Hot answers tagged

31

This question is quite broad by specifying a sudden fall to cryptanalysis and therefore my answer might not be as complete as you wish it to be. If by "become practically attackable, or close enough that use is strongly discouraged" you imply not an academic breach but assume a weaker attacker such as a single ciphertext attack, then there are quite a few ...


28

You could be thinking about the Merkle-Hellman knapsack cryptosystem. It was invented in 1978 and everything seemed well and good until it was completely broken six years later in 1984 by Shamir - it was a complete and total break, i.e. the cryptosystem became unusable overnight. That said I don't know if the knapsack cryptosystem was ever "popular" in the ...


25

What methods would they use? Since WW2, we know the security of Enigma machines was weakened by the reflector, resulting in two problems: No difference between en- and decryption, which means that if K ↦ T, then T ↦ K. No letter can be encrypted by itself because electricity can not travel the same way back, which results in a reduction of encryption ...


22

I sent an email to Ron Rivest and got an answer back. The digits of $\pi$ are used as a sort of random number generator that is used in the Durstenfeld shuffle (see also Knuth vol 3, sec 3.4.2). Below is some pseudocode adapted from the description and code he sent me. S = [0, 1, ..., 255] digits_Pi = [3, 1, 4, 1, 5, 9, ...] # the digits of pi def rand(...


18

DES has not been mentioned in the previous two answers. Although it was known to be quite weak from very early on it was widely used for a couple of decades at least, until newer algorithms (3DES, AES, but also e.g. RC4) displaced it. Nowadays it can be broken in hours with dedicated hardware or with at most a few thousand dollars of cloud computing time. ...


17

In 1911, there was no computer either. With much more modest goals of security for the next few months, the German army came up with the Enigma, which was broken. Before the 1970s, cryptography was essentially a military-only domain, so there were no "openly collaborating knowledgeable experts". The situation was qualitatively different. So it is a bit ...


17

This is a shot in the dark, but could you be thinking of the Needham-Schroeder protocol? It was published in 1978 [1], and an attack was published as much as 18 years later, in 1996 [2]. It is not an encryption method, though, but a protocol. In fact, the original paper does not even specify an encryption method to be used, but uses encryption symbolically. ...


10

It really depends on how you define the problem. The One-Time-Pad was invented in 1882, so a well designed storage scheme using a OTP would probably still be secure today. The Vigenère cipher is basically a OTP that uses a caesar shift over the letter determined by some key. In practice these keys were often letters or rare books. A small subset of ...


10

The answer is yes, non-US ciphers exist and are in fact very popular. Actually, some who are looking for alternatives, opt for non-NSA/NIST ciphers, for instance Salsa/ChaCha from DJB (who is US citizen). A lot of ciphers have been developed in EU and Japan. China definitely has developed ciphers for its own use, just like many other countries. But long ...


9

Parity of DES key bytes was introduced on request of US authorities during the design of DES in the late 1970s: it mitigates the risk of accidental key alteration; in particular, any all-zeros or all-ones byte of the key is rejected by the mandatory odd parity check, and any one-bit alteration is caught, which are advantages from a functionality ...


8

Plenty of ciphers come out of the USA from government research or selection competitions. AES and DES are examples. Indeed, the US is known from some crypto-related competitions that were/are open to anyone and they surely will do ample of government research related to cryptology, but you need to be sure that you differ between “they selected it” and “...


8

Prompted by Paŭlo's comment, I took a look at the original requirements set out for the AES candidates. A useful page for that turns out to be AES - The Early Years (1997-98) on the NIST web site (and surprisingly hard to find there; the internal links are broken and Google doesn't find it either). The AES key lengths were specified in the original Request ...


7

Even though Dobbertin could not provide a real collision of MD5, I would say that Hans Dobbertin first publicly described MD5 collision(s) in "The Status of MD5 After a Recent Attack" (PDF) – that was in 1996. To the best of my knowledge he was one of the first who recommended to no longer use MD5 when collision-resistance is needed/expected/required. On ...


7

I won't answer your question up to every detail, as I would have to write a book to answer the pretty broad question to full length. But I'll give you some hints as it would be wrong to let you think that non-military cryptography has appeared in 50's and 60's only thanks to leaks from the NSA! Before the 30's… One of the earliest descriptions of ...


7

As an Iranian Cryptology student in one of the most well-known Iranian Universities called Sharif University of Technology, I want to add this to the answers. There doesn't seem to be any National Standard Cipher here in Iran. But It doesn't mean that there shouldn't be any classified cipher being used by the military or the revolutionary guards. As I am ...


7

They are there to check if the key was indeed correctly retrieved. It could for instance be that the key is a result of key decryption or key agreement. In that case, or simply during transmission, wrong keys are used. According to NIST FIPS 46-3: The 8 error detecting bits..." Or even better, Wikipedia states ANSI INCITS 92-1981), section 3.5: One ...


6

Wrapping up my comment as an answer: Imagine you’re a Japanese cryptanalyst in the year 1944. There is no such thing yet called “television”, and you’re still decades away from a wordwide network feeding you with all the knowledge you could wish for. In that case there’s only a minimal chance you’ve ever heard or seen a Navajo. So, you’ll be wondering ...


5

There is a full breakdown of key size on a website talking about the “Technical Details of the Enigma Machine”. To sum up: If all rotor combinations are included then you have a possible $3*10^{114}$ possible keys. However, that didn't happen (the operators would need to keep $\frac{26!}{26}=1.5*10^{25}$ rotors at hand if they didn't allow repeats). By ...


5

The first publication of an MD5 collision was on 17-Aug-2004 17:44 UTC on the eprint archive server: Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu, Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD (third version). The results where fresh: the authors had just corrected IV endianness, that they got reversed in two earlier versions. Like 8 ...


5

I don't understand why this is important, but just want to note that the collision was first presented at the rump session at CRYPTO 2004, and was then later published. The earliest time-stamp is an ePrint report by Xiaoyun Wang and Dengguo Feng and Xuejia Lai and Hongbo Yu, called Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. The date is ...


5

It looks like with no leakage or errors, Enigma is still secure. Quoting the Enigma@Home project website: Enigma@Home is a wrapper between BOINC and Stefan Krah's M4 Project. “The M4 Project is an effort to break 3 original Enigma messages with the help of distributed computing. The signals were intercepted in the North Atlantic in 1942 and are believed ...


5

The paper you link to in your comment is a fictional paper where the author (inspired by experiences with reviews he got for his own papers) imagines how negative reviews to groundbreaking papers could have looked like. So its just fun ;) AFAIK the RSA paper has never been rejected (but the very first paper of Ralph Merkle on public key crypto got rejected, ...


5

As I noted in another answer, Auguste Kerckhoffs published his principles in the scientific/academic journal “Journal des sciences militaires, vol. IX, pp. 5–38 in his article "II. DESIDERATA DE LA CRYPTOGRAPHIE MILITAIRE.", Jan. 1883. So, when you ask since when academics and cryptographers “might” have been accepting (and even applying) those rules, the ...


4

No, the idea is much older. Don't trust the movie too far, Turing actually searched for the word "eins" (one) because it was the most common number used. Far more likely to appear than "Heil Hitler" but it doesn't make good screen drama.


4

Yes. The Serpent Cipher was developed outside of America, and isn't maintained by an American group. It came in 2nd place during the AES competition. It has a higher safety factor than AES (Rijndael), but isn't as fast. And there are stream ciphers being developed and validated by eSTREAM in Belgium. The Salsa20 stream cipher, by American cryptographer ...


4

I think the first paragraph of this document show be helpful. The Rabin reference at the bottom of the text is from 1978, and the impression I get from p3 of this document is that he came up with a linear iterated hash function in that 1978 paper. So maybe Rabin invented it. I think we can be pretty sure it was either Merkle, Rabin or Yuval (if you must ...


4

A problem with this message is that the image in a press release from GCHQ differs slightly from one in a New York Times article, although the paper, with its tears looks the same. The image below shows the two side by side, the one on the left from the NY Times and the right from GCHQ. There is a slight difference in the style of writing, i.e. more sloping ...


4

In 2006-07, NIST published a new standard for cryptographically secure random number generation. One of their suggestions was based on elliptic curves, DUAL_EC_DRBG. in 2006, Daniel Brown and Kristian Gjosteen discovered that this algorithm had a subtle bias for certain numbers. Later, in 2007, Dan Shumow and Niels Ferguson said they had found what caused ...


3

I believe that the key lies in the final 6 number 1525/6. In this period the German Mathematician Albrecht DÜRER published "The Four Books on Measurement" the third of which picks up on the geometric construction of the latin alphabet. Albrecht DÜRER was also famous for a magic square which is the same as Sudoko puzzles and would therefore have the ...


3

If the school has graduate courses that interest you and you think you can do well in (i.e. for comprehensive exams), and there is a strong crypto research group there, I would recommend any school that satisfied these criteria. As you move through academics, it becomes more and more clear that the quality of your research is the most important, and it is ...



Only top voted, non community-wiki answers of a minimum length are eligible