A Modern Reappraisal of the One-Time Pad Cipher.
in [Cryptography]
|
Prev: A Randomness Hypothesis.
Next: How cool is this?
From: Simon Johnson on 12 May 2010 17:52 > Realizing a practical-as-possible OTP is an interesting and worthwhile > project. The 'adacrypt' context here is obviously worse than useless. > Somewhat ironic that after all the effort sci.crypt has put into > explaining to the math-deniers the limits of the OTP, we still don't > have an OTP implementation anywhere near as practical as we know how > to build. > I think you nearly got it and went astray on that last paragraph. The cryptographic community did exactly what you suggested. They built a workable one-time pad implementation. It's called a stream-cipher. Cheers, Simon.
From: unruh on 12 May 2010 19:28 On 2010-05-12, Simon Johnson <simon.johnson(a)gmail.com> wrote: > >> Realizing a practical-as-possible OTP is an interesting and worthwhile >> project. The 'adacrypt' context here is obviously worse than useless. >> Somewhat ironic that after all the effort sci.crypt has put into >> explaining to the math-deniers the limits of the OTP, we still don't >> have an OTP implementation anywhere near as practical as we know how >> to build. >> > > I think you nearly got it and went astray on that last paragraph. > > The cryptographic community did exactly what you suggested. They built > a workable one-time pad implementation. > > It's called a stream-cipher. Except it is not a one time pad. The key advantage of a OTP is that every character is completely underivable from an arbitrary number of previous (or later )characters. this is not true of a stream cypher. Assuming a 128 bit key, once you have 16 characters you have a very high probability of predicting all the rest, by exhaustive search of the key space. Now, whether or not that is practical is irrelevant. It says that 16 characters determine all the rest of the characters. > > Cheers, > > Simon.
From: Greg Rose on 13 May 2010 00:24 In article <slrnhumecj.ttm.unruh(a)wormhole.physics.ubc.ca>, unruh <unruh(a)wormhole.physics.ubc.ca> wrote: >On 2010-05-12, Simon Johnson <simon.johnson(a)gmail.com> wrote: >> >>> Realizing a practical-as-possible OTP is an interesting and worthwhile >>> project. The 'adacrypt' context here is obviously worse than useless. >>> Somewhat ironic that after all the effort sci.crypt has put into >>> explaining to the math-deniers the limits of the OTP, we still don't >>> have an OTP implementation anywhere near as practical as we know how >>> to build. >>> >> >> I think you nearly got it and went astray on that last paragraph. >> >> The cryptographic community did exactly what you suggested. They built >> a workable one-time pad implementation. >> >> It's called a stream-cipher. > >Except it is not a one time pad. The key advantage of a OTP is that >every character is completely underivable from an arbitrary number of >previous (or later )characters. this is not true of a stream cypher. >Assuming a 128 bit key, once you have 16 characters you have a very high >probability of predicting all the rest, by exhaustive search of the key >space. Now, whether or not that is practical is irrelevant. It says that >16 characters determine all the rest of the characters. A minor nit: if the state of the stream cipher is only 128 bits, time-memory-tradeoff attacks would be surprisingly efficient, so all modern stream ciphers have a larger state than keyspace. See the EStream project for more details on this. But your point remains, that maybe 32 bytes would allow an efficient brute force attack. 16 might not be sufficient. The complexity would still be 2^128, just rainbow tables etc wouldn't help. Greg. PS. Isn't it nice to have substantive discussions? Please stop feeding trolls, everyone. --
From: unruh on 13 May 2010 01:12 On 2010-05-13, Greg Rose <ggr(a)nope.ucsd.edu> wrote: > In article <slrnhumecj.ttm.unruh(a)wormhole.physics.ubc.ca>, > unruh <unruh(a)wormhole.physics.ubc.ca> wrote: >>On 2010-05-12, Simon Johnson <simon.johnson(a)gmail.com> wrote: >>> >>>> Realizing a practical-as-possible OTP is an interesting and worthwhile >>>> project. The 'adacrypt' context here is obviously worse than useless. >>>> Somewhat ironic that after all the effort sci.crypt has put into >>>> explaining to the math-deniers the limits of the OTP, we still don't >>>> have an OTP implementation anywhere near as practical as we know how >>>> to build. >>>> >>> >>> I think you nearly got it and went astray on that last paragraph. >>> >>> The cryptographic community did exactly what you suggested. They built >>> a workable one-time pad implementation. >>> >>> It's called a stream-cipher. >> >>Except it is not a one time pad. The key advantage of a OTP is that >>every character is completely underivable from an arbitrary number of >>previous (or later )characters. this is not true of a stream cypher. >>Assuming a 128 bit key, once you have 16 characters you have a very high >>probability of predicting all the rest, by exhaustive search of the key >>space. Now, whether or not that is practical is irrelevant. It says that >>16 characters determine all the rest of the characters. > > A minor nit: if the state of the stream cipher is > only 128 bits, time-memory-tradeoff attacks would > be surprisingly efficient, so all modern stream > ciphers have a larger state than keyspace. See the > EStream project for more details on this. I am not sure that it matters. Given 16 bytes, what is the chance that more than one key would give those same 16 bytes? If we assume that the stream produces random bits, then teh probability that the 128 bits would occur for two different keys would be of order 2^-128. But I agree that it might require a bit more than 16 bytes to make sure. > > But your point remains, that maybe 32 bytes would > allow an efficient brute force attack. 16 might > not be sufficient. The complexity would still be 2^128, > just rainbow tables etc wouldn't help. > > Greg. > > PS. Isn't it nice to have substantive discussions? > Please stop feeding trolls, everyone.
From: Simon Johnson on 13 May 2010 09:00
On May 13, 12:28 am, unruh <un...(a)wormhole.physics.ubc.ca> wrote: > On 2010-05-12, Simon Johnson <simon.john...(a)gmail.com> wrote: > > > > >> Realizing a practical-as-possible OTP is an interesting and worthwhile > >> project. The 'adacrypt' context here is obviously worse than useless. > >> Somewhat ironic that after all the effort sci.crypt has put into > >> explaining to the math-deniers the limits of the OTP, we still don't > >> have an OTP implementation anywhere near as practical as we know how > >> to build. > > > I think you nearly got it and went astray on that last paragraph. > > > The cryptographic community did exactly what you suggested. They built > > a workable one-time pad implementation. > > > It's called a stream-cipher. > > Except it is not a one time pad. The key advantage of a OTP is that > every character is completely underivable from an arbitrary number of > previous (or later )characters. this is not true of a stream cypher. > Assuming a 128 bit key, once you have 16 characters you have a very high > probability of predicting all the rest, by exhaustive search of the key > space. Now, whether or not that is practical is irrelevant. It says that > 16 characters determine all the rest of the characters. > > Except it is not a one time pad. The key advantage of a OTP is that > every character is completely underivable from an arbitrary number of > previous (or later )characters. this is not true of a stream cypher. I fully understand the difference between a stream cipher and the one- time pad (OTP). The theorem that applies to the OTP does _not_ apply to stream ciphers. However, my argument is more subtle than you give me credit for. My argument is that the OTP has, in practice, provides less security than AES in CTR mode. For some reason this appears to be controversial; perhaps in the same way the modern evolutionary synthesis is to some Christians. The OTP is secure if and only if the bits are independent and the probablity of a 1 or 0 is 50%. The proof of security is predicated on the fact that you can achieve such a distribution. My assertion is that this no easier than developing a secure cipher by conventional methods. Nobody doubts that you can fulfill such a distribution with small cryptograms. But by the same token, nobody believes AES could be solved with a megabyte of chosen plaintext. For larger cryptograms the strength of the OTP is not assured. As I discussed elsewhere in the thread, how do you prove a given (real) random number generator (RNG) does fufill this distribution over hundreds of millions of bits? How do you verify there isn't some higher order bias invisible to Diehard or whatever series of tests you decide to run? How are you certain that bias is not produced by the arrangement of transistors and resistors in the circuit you devised? That, to me at at least, seems as much as an imponderable as verifying AES is completely secure mathematically. Then there's the fact the AES has serious advantages. It has a smaller key and those keys can be re-used. Most people would agree that we can easily generate 128-bits of entropy. The OTP provides perfect security provided the RNG is perfect. In contrast, mainstream crypto-systems doesn't require a perfect RNG. It can actually tolerate pretty high levels of bias before security completely fails. Moreover, the security depends on small, easily kept, secrets. The OTP just replaces the problem of assuring secrecy with the equally big problem of generating large amounts of random bits and transporting them the interested parties. The OTP is uselessly perfect. Cheers, Simon |