This page contains errata and addenda of:
Reinhard Wobst, "Abenteuer Kryptologie", 3rd edition
Addison-Wesley Verlag 2001, ISBN 3-8273-11815-7
(simple page numbers)
Reinhard Wobst, "Kryptologia"
Wydawnictwo RM Warszawa 2002, ISBN 3-8273-11815-7
(page numbers ending with "p")
Last modification: @(#) Mar 09 2005, 10:57:37
Nobody is perfect, and thus also the 3rd edition of this book will contain errors - it was modified strongly. I will always be glad about hints, but I beg you not to send me "uncrackable codes " or "completely new algorithms". You can read in the preface, why.
Many readers of the first tow editions could not contact me since the mail address r.wobst@addison-wesley.de vanished after Addison-Wesley was joined to Pearson Education; there seemed to be no way to reactivate it. My new address which will hopefully be valid for a long time is: r.wobst @ gmx.de (without spaces).
NEW (03/09/2005): 2.2.1 - Automatic decryption of substitution ciphers
NEW (10/22/2004) 6.2.2: I wrote a software for secret sharing myself.
NEW (12/9/2004) 6.3.1: Successful attacks on hash functions
2.2.1 - Automatic decryption of substitution ciphers
My ideas described in this chapter did not work in practice. Meanwhile I wrote a Python script, based on word patterns, which quite reliably decrypts ciphertexts of at least 200 characters; no statistics are used. The script was developed for UNIX/Linux but should be portable to other systems without difficulties. You can find the 13KB long archive (with documentation included) on subscrack.zip German users can also download an 800KB long compressed dictionary: wordlst.gz
2.2.4 - "Stabchiffrierung" (szyfrowania przy użyciu wałka)
The stick described at the beginning of this paragraph does not stem from ancient Greece but from Spartan and was called skytale (cf. [KahnCode], "The first 3000 years").
2.5.2 - Enigma
Only in 2000 Great Britain disclosed further secrets of Enigma, 55 years after end of World War II. It turned out that ten machines of type "Colossus II" were used; they might also be entitled as first electronic computers in history since they were programmable to some extend. Officially, the machine ENIAC built in USA in 1946 is considered as the first computer. More details in
www.telegraph.co.uk/et?ac=003549412141223&rtmo=aqJ4XahJ&atmo=tttttttd&pg=/et/00/9/7/ecfcol07.html and www.telegraph.co.uk/et?ac=003549412141223&rtmo=wAfMMQKb&atmo=gggggg3K&pg=/et/00/9/30/ncol30.html .
4.5.3 - RSA: Connection between factorization and discrete logarithm
On page 165 below, a heavy error: To compute m from me of course does not mean to compute a discrete logarithm but to compute the e-th root. Obviously, this is not simpler. Also the computation of modular square roots is a "hard problem".
But in general, computation of discrete logarithms is not easier than factorization (cf. e.g. [MenOOVan, 3.78]). The proof is not so simple as claimed in the book.
5.4.4 - RC6
Since RC6 had not been approved as AES standard, RSA Security nevertheless patented this algorithm - we are sorry. This was not clear yet when the book was finished.
5.5 - Cryptanalysis of AES (Rijndael)
There is a paper of Niels Ferguson, Richard Schroeppel and Doug Whiting (May 2001) which is of "alarming interest". It gives an astonishingly simple representation of the Rijndael transformation in form of a sum of continuous fractions. Though there are 225 continuous fractions to sum up on each side of the equation ... But when somebody deduces an attack from this, it might even be practicable. For cryptologists this should look alarming. It could be that the worries about the simple structure of Rijndael were reasonable.
There are different reactions on this paper, but now (2004), there seem to be no important new conclusions based on this paper. You can find it in http://www.xs4all.nl/~vorpal/pubs/rdalgeq.html
- supposed you have some mathematical knowledge.
Moreover, I would like to thank the Polish reader Pawel Krawczyk for the hint on
and
There you can find more promising ideas of Rijndael cryptanalysis. Opinions about these papers are diverging. In c't 21/2002, p.38, and in iX 12/2002, pp.100-104 (both Heise Verlag, Germany) there were two articles of mine about this topic with more details. Properly speaking, it was rather early to write about this, but it will anyway be better than waiting for bad rumors.
Should this kind of algebraic attacks be successful some day, then ciphertext attacks with few blocks could be possible! On the other hand, scientists still dispute where such approaches have a chance at all. But AES seems to be "algebraically threatened" nevertheless. My tip: Twofish.
5.6 - RC4
In Schneier's book "Applied Cryptography" you will find a somewhat different definition for the generation of the internal key (figure 5.21 n my book). There the index runs from 0 to 256. I am not quite sure whether Schneier's description is equivalent to my version, but my version stems from the generally used C programs what means that it passed the "practical test".
On www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html , there is a review of actual RC4 cryptanalysis. It shows that this algorithm can be attacked in many implementations, especially in the WLAN standard 802.11.
5.7.1 - pkzip encryption
On p.242/222p, there should be
K = LSB((2b+5)a) + MSB((b+2)(b+3))
The attack works nevertheless - (2b+5) is also prime to 256, and a can be computed from b.
5.7.2 - Listening to mobile GSM phones
My statement on page 249/229p that two minutes of listening suffice to decrypt a GSM call, is not correct. You need bold: the "output of A5/1" during two minutes, i.e. plaintext AND ciphertext! The alternate option is "two seconds plaintext and several minutes computing time". I do not know whether one can deduce a practicable attack from this (maybe, using enciphered, known header data?). Biryukov, Shamir and Wagner explicitely "make no statement about the security of GSM systems".
However, in 2003 Barkan, Biham and Keller found highly efficient and practicable attacks against the weaker algorithm A5/2, cf. http://cryptome.org/gsm-crack-bbk.pdf . Here the authors used that error correction codes are also encrypted. This establishes an algebraic dependency between parts of the ciphertext. In practice, this looks as follows:
With the help of some IMSI-Catcher (i.e., "man in the middle") you make the phone use A5/2 instead of A5/1 (almost all phones can do this). Then you listen few hundredth of seconds (!) and need about one second for decryption. But as far as I know, phones switch off decryption completely on demand, and almost nobody will take notice ...
5.9 - quantum computers
There is a nice book about this topic, easy to understand:
Colin P.Williams, Scott H.Clearwater,
Ultimate Zero and One
Copernicus/Springer, New York 2000
ISBN 0-387-94769-8
In my book, the principle of quantum computers was explained a bit too simple. The ideal state that the solution has probability 1 can not always be achieved. However, with the help of quantum computers one can obtain periods of functions directly, similar as one deduces crystal structures directly from X ray diffraction photos. Based on such principles, the Shor algorithm for factoring large number would work, as explained in the book cited above.
It is true that entangled quantum states are influenced simultaneously and without any delay, but this does not allow to conclude on computing times. The IBM "computer" from August 2000 obviously based on five nuclear spins where the nuclei were coupled via the electron sheath. The necessary radio pulses (corresponding to one computing step) have a length of several milliseconds. In spite of this apparently long time - could one couple 512 nuclei in this manner, 2512 states would be processes at the same time, what is an unbelievable large number.
Meanwhile IBM researchers constructed a 7 bit quantum computer based on the same principle, and they could factor the number 15: http://www.research.ibm.com/resources/news/20011219_quantum.shtml.
CNN announced on Feb 17th, 2001 big progresses with the help of laser technology. But this does not concern cryptography. This technology obviously suites only for applications without entangled quantum states (but just they are important for factorization and discrete logarithm computation). It will be rather useful for search in unordered data files. Because of the physical principle, however, I have doubts whether this method can search in trillions of entries - accidentally, I have some knowledge in acusto-optics ...
More: www.scienceagogo.com/news/20010417230843data_trunc_sys.shtml.
A very good, very interesting link about so-called QIS (quantum information science) can be found here: www.nsf.gov/pubs/2000/nsf00101/nsf00101.html
5.10 - Power Attack
Designers keep up with the cryptanalytics: In www.cs.cornell.edu/cs789-fa99/rohatgi.htm you will find some information about IBM smart cards that are immune against SPA and even DPA.
6.2.2 - Secret Sharing software
Meanwhile there are free implementations of secret sharing, though all I found up to now are rather for demonstration purposes:
www.ts-networld.de/documents/secshare
The young cryptologist Sebastian Mozejko from Poland was so kind to send me links to essentially better software:
axion.physics.ubc.ca/crypt.html#SECSPLIT
www.afn.org/~afn21533/rgdprogs.htm#SECSPLIT
www.atomicfrog.com/knowledge/security/misc/
This C program was tested under DOS and UNIX, but it uses IDEA. One should exchange the algorithm.
NEW: Therefore I started myself to develop an easy to use Python class that allows to create and use arbitrary "K of N" schemata. By default, it can encrypt and decrypt data in memory (strings in the sense of Python), files and data streams. The encryption itself is done by an external C program that uses Blowfish-128 oder AES-128 (and the OpenSSL library libcrypto). As usual, the shared secret acts as master key (KEK, key encryption key) only, the encryption itself is done with a random session key. Moreover, integrity is checked with the help of an MD5 hash sum (what is secure in this context, see below).
Python suites very well for such applications since it implements a fast big number library. Moreover, it is a modern and extremely easy to learn language with interfaces to C/C++ and other languages, cf. www.python.org. Thanks to plenty modules almost all wishes can be fulfilled (there is no reason to do anything in Perl; Python programs are normally much better to maintain and much better to understand).
Download: As zip archive secshare.zip of the three file secshare.py, secshare.txt and enc_stream.c.
NEW: 6.3.1 - Successful attacks against hash functions
On CRYPTO '04, first time collisions of MD5 and SHA-0 were shown. The Chinese Wang, Feng et al. told that for computations of an MD5 collision, a PC would need between 15 seconds and 5 minutes. This is a sensation, especially if one regards how long this has been tried. The French Joux needed a little bit longer to compute his SHA-0 collision, namely 80.000 hours on Itanium2 CPUs. - SHA-0 differs from SHA-1 (called SHA in my book) only by a 1-bit left rotation during text expansion. There are no known attacks against SHA-1. But the progress alarmed the scientists, and more interesting results are to be expected soon. One of them is the result of Kelsey and Schneier that the search for a second preimage (i.e., Y with sha(Y) = sha(X) for given X) requires about 2n/2 instead of 2n computations for classes of hash function to which also belongs SHA-1.
I would not acknowledge digital MD5 signatures any more. But HMAC sums (which depend on a secret key) a probably unaffected. It will also be secure if hashsums are encrypted together with the plaintext (as is the case in my secret sharing software, see above). But one should have serious doubts about the long time validity of recent digital signatures.
Sources:
www.md5crk.com/sha0col/
(SHA-0 collision)
eprint.iacr.org/2004/199.pdf
(paper of Feng, Wang et al.)
eprint.iacr.org/eprint/2004/207
(investigation of SHA-1 successors)
md5coll.py
(my Python script checking the MD5 collision)
eprint.iacr.org/eprint/2004/304
(paper by Kelsey and Schneier about second preimages)
Probably, in the German journal c't (Heise Verlag), there will be an article of mine end of 2004 of beginning of 2005 about this topic.
zu 6.5.3 - RSA SecurID Token
Another hint from Sebastian Mozejko from Poland: They attack the hash function inside the RSA SecurID Token, cf. http://eprint.iacr.org/2003/162/ and .../205/. I had no time yet to read this in details. Probably, the attack is not dangerous since the costs seems to be very high, and other attacks like man in the middle could be more effective.
zu 7.1.4 - PGP and GnuPG
Meanwhile there are Windows versions of GnuPG, and a project "aegypten" was started that shall join the worlds of S/MIME and X.509. More in www.gnupg.org .
After NAI stopped the development of PGP (and some other products like PGPdisk), finally PGP was selled. Details can be found in the journal article "Auferstanden" (iX 2/2003, S.48-52) of I.Camphausen and S.Kelm about PGP 8 (in German).
In general, I am still sad when I think about mail encryption.
On the other hand, the German ministry for economy supplies the application and distribution of GnuPG also under Windows. This initiative is called "Gnu Privacy Project GnuPP": (www.gnupg.org)
7.2.1 - Attacks on hierarchical PKI structures
My attack on hierarchical PKI structures (where a secret service obtains a private key) seems to be less known. However, the secret service must provide that the "victim" also gets the wrong public key. I guess that this attack can be prevented by modifications or extensions of the standard.
8.2.1 - Echelon
The Echelon committe of European Union shuts up its work. You can find the report in http://cryptome.org/echelon-ep.htm and http://www.europarl.eu.int/tmpcom/echelon/prechelon_en.htm . In http://www.telepolis.de/deutsch/special/ech/7428/1.html there is an interesting interview with the commission speaker Gerhard Schmid.
The existence of Echelon is not denied any more, but the topic is still changing rapidly.
They tried to exceed Echelon by orders of magnitude with the initiative "Total Information Awareness" (TIA), cf.
www.darpa.mil/iao/index.htm
www.heise.de/tp/deutsch/inhalt/te/13580/1.html
online.securityfocus.com/columnists/126
and in more popular form in "Das Auge Gottes ist noch ziemlich trübe", Computer Zeitung 5/2003, p.8 (in German). Recently (Oct 2004) it looks as if components of TIA are pushed to practice, TIA itself is disliked by the parliament.
8.2.3 - Key escrow
After the terror attacks of Sep 11th, 2001, this unfortunate topic was discussed again. But key escrow is useless in fighting terrorism. The arguments in my figure are fairly incomplete. For instance, nobody can imagine now (and it will not be possible) to change all software and protocols like SSL, IPSEC, VPNs, OpenPGP, S/MIME etc. Also any international agreement is unrealistic, think about the fear of Echelon and industry espionage. I published three articles about this (iX 3/2002, LanLine spezial VI/0, UNIX/open 3/02). Obviously, one has to be prepared for discussions all over the time since many people with heavy influence require key escrow again and again.
Trojan cryptography and Microsoft
In the LAN protocol Kerberos for encrypted data exchange over LANs, some header fields are free. However, Windows 2000 used these fields and thus was incompatible to non-Microsoft computers. As usual with Microsoft software, the information contained in these fields was not documented. There was even a complaint of Microsoft against Slashdot who discovered this modification as first. Topic of this complaint: Unauthorized disclosure of internals.
I don't know whether this is Trojan cryptography, but until disclosure of all details one has to assume it. This of similar examples in the Microsoft world (as inserting GIDs in word documents, online transfer of this ID to Microsoft during Windows registration etc.)
In spite of this, all will be use Kerberos under Windows 2000 and will wonder why this protocol does not interoperate with other, "exotic", computers.
(for the Polish edition, cf. the German version of this web site for German misprints)
p.150 above, 2.: The last sentence is wrong since we need that e is prime to p-1 and q-1, not to p and q. It can happen that several primes have to be tested.
p.227 middle: IEEE instead of IEE
p.234 below: Skipjack instead of IDEE
p.281, after headline 6.4: 5.7.5 instead of 5.6.5
p.312, middle: fig. 6.10 instead of 7.1
Different pages: Write "Hellman" instead of "Hellmann".