Tečaj iz kriptografije in računalniške varnosti - 4. mar. 2008

Povzetek predavanja:

Klasična kriptografija (1. poglavje):

• zgodovina: nekaj anekdot (ta del si preberite sami)
• transpozicijski tajnopisi, afini tajnopisi, Vigenerjev tajnopis, Hillov tajnopis (preberite sami), (primer tokovnega tajnopisa), LFSR.
• napadi (Kerckhoffov princip, nivoji: samo tajnopis, poznani tajnopis, izbrani čistopis, izbrani tajnopis)
• tokovnege šifre in primer LFSR

• popolna varnost, računska varnost, brezpogojna varnost, dokazljiva varnost (ne bi škodilo prebrati še kaj o pogojni verjetnosti in Bayesovi formuli)
• Vernamov enkratni ščit
• predlagano dodatno branje:
  • entropija
  • lastnosti entropije
  • ponarejeni ključi in enotska razdalja
• Produktne šifre

Simetrični kriptosistemi (pričetek 3. poglavja)

• nekaj zgodovine: DES, AES
• iterativne šifre, zamenjalno-permutacijske mreže
• produktni tajnopisi in Fiestelov tajnopis
• opis DES-a
• načini delovanja (opozorilo: DES šifrirna funkcija E_K se uporablja tako za šifriranje kakor tudi za odšifriranje v CFB in OFB načinu)
• naivni/požrešni napadi in velika števila
• 3-DES in DESX

Dodatna gradiva:

• Rajko Jamnik, Elementi teorije informacije, DMFA Slovenije, 3. natis, Ljubljana 1987.
• nekaj statistike o slovenskih črkah.
• C. A. Ronce, Feedback Shift Register, LNCS169, Springer-Verlag, Berlin, 1984.
• E. S. Selmer, Linear Recurrence Relations over Finite Fields, University of Bergen, Norway, 1966.

• Ameriški kriptološki muzej:

  Nekaj slik iz NSA muzeja.
  The National Cryptologic Museum is the National Security Agencys principal gateway to the public. It shares the Nations, as well as NSAs, cryptologic legacy and place in world history. Located adjacent to NSA Headquarters, Ft. George G. Meade, Maryland, the Museum collection contains thousands of artifacts that collectively serve to sustain the history of the cryptologic profession. Here visitors can catch a glimpse of some of the most dramatic moments in the history of American cryptology: the people who devoted their lives to cryptology and national defense, the machines and devices they developed, the techniques they used, and the places where they worked. For the visitor, some events in American and world history will take on a new meaning. For the cryptologic professional, it is an opportunity to absorb the heritage of the profession.

  Originally designed to house artifacts from the Agency and to give employees a place to reflect on past successes and failures, the Museum quickly developed into a priceless collection of the nations cryptologic history. The Museum opened to the public in December 1993 and quickly became a highlight of the area. Being the first and only public museum in the Intelligence Community, the Museum hosts approximately 50,000 visitors annually from all over the country and all over the world, allowing them a peek into the secret world of codemaking and codebreaking. The Museum is also an invaluable educational tool, benefiting thousands of students and teachers every year. Tours are provided allowing students of all ages the chance to learn about cryptologys impact on history and the possibility of exciting jobs in an area they may not have thought possible.

  • Debata o večkratnem zaporednem šifriranju s simetričnim kriptosistemom:
    Burton S. Kaliski, Jr and M.J.B. Robshaw, Multiple Encryption: Weighing Security and Performance, Dr. Dobb's Journal, January 1996.
  • "A Performance Comparison of the Five AES Finalists" B. Schneier and D. Whiting, Third AES Candidate Conference, 2000. In 1997, NIST announced a program to develop and choose an Advanced Encryption Standard (AES) to replace the aging Data Encryption Standard (DES). NIST chose five finalists in 1999. We compare the performance of the five AES finalists on a variety of common software platforms: current 32-bit CPUs (both large microprocessors and smaller, smart card and embedded microprocessors) and high-end 64-bit CPUs. Our intent is to show roughly how the algorithms' speeds compare across a variety of CPUs. Then, we give the maximum rounds cryptanalyzed for each of the algorithms, and re-examine all the performance numbers for these variants. We then compare the algorithms again, using the minimal secure variants as a way to more fairly align the security of the five algorithms.

    http://www.counterpane.com/aes-comparison.html

    AES uporablja ameriška vlada

  • Po odkritju diferencialne kriptoanalize je Don Coppersmith priznal, da je IBM v resnici poznal ta napad (ne pa tudi linearno kripto-analizo) že ko so razvijali DES. V naslednjem članku je odkril nekatere kriterije, ki so jih uporabili pri konstrukciji. V zvezi s tajnostjo teh kriterijev je povedal naslednje:
  ``Po posvetovanju z NSA, smo se zavedali, da utegne objava kriterijev načrtovanja odkriti tehniko kripto-analize. To je močno sredstvo, ki se ga da uporabiti proti mnogim tajnopisom. To bi zmanjšalo prednost ZDA pred drugimi državami na področju kriptografije.''
  ``Mnogi so predvidevali, da se za prikrivanjem skriva kakšna zanka ali prikrita slabost DES-a. Eden od namenov tega članka je ovreči to misel. Razlog, da to ni bilo objavljeno, je pravzaprav v skrivanju prednosti, ne v skrivanju slabosti.''
  • D. Coppersmith, "The Data Encryption Standard (DES) and its strength against attacks", IBM Journal of Research and Development, volume 38 (1994), 243-250.
  • D. Coppersmith, "In defense of DES", preprint, 1992.
  • Mike Wiener, Efficient DES Key Search (ps datoteka).

• RSA je objavil DES Challenge II v katerem izziva k dešifriranju, da bi tako ocenili pravo vrednost iskanja s preskušanjem vseh možnih ključev. V tem drugem izzivu je tudi opis vsega dela, ki je sledilo prvemu izzivu: DES Challenge I, in je pripeljalo do rešitve 17. junija 1997. 

• Kakšno varnosti potrebuje kdo?
• Report (ASCII datoteka) by Blaze, Diffie, Rivest, Schneier, Shimomura, Thompson, and Wiener on minimal key lengths for symmetric ciphers to provide adequate commercial security.
• NIST je objavil (ASCII datoteka) pričetek razvoja novega FIPS standarda za šifriranje s simetričnimi ključi.

• Dobre čenče o NSA (National Security Agency) lahko najdete v naslednjem poročilu:
• J. Bamford, The Puzzle Palace: A Report on America's Most Secret Agency, Houghton Mifflin, Boston, 1982.

Domače naloge:

• 2. domača naloga (do 10. mar.)

• Pokaži, da je produkt dveh idempotentnih šifer, ki komutirata, pravtako idempotentna šifra.
• Napad na 2-DES: naivno/požrešno iskanje k-bitnega ključa dvojnega šifriranja (npr. 2-DES) preveri 2^2k parov ključev. Kako lahko bistveno izboljšamo to iskanje?