Comment Putting the Kabosh on Rabin's "Unbreakable" Crypt (Score 1) 241
There are several assumptions in what I garner from Rabin's press release(s). And, as we all know, it is often the assumptions that are the holes in any plan. I'm not going to target the "secret forever" problem - i.e. a message is discovered in a house and it's encrypted with Rabin's code, but rather the real-time problem: The encrypted message is being intercepted via a man-in-the-middle attack. I target this because the only real use of this cryptographic scheme is real-time traffic; otherwise no one can ever translate the message (might as well just write over your message with the random stream) because they won't have access to a random stream from some time past. And if they DID, well, that would mean someone is storing the stream - expressly against the design of the algorithm and destroying it's one strength.
As a few others have pointed out (adamwood, KFury, etc), the start code is probably the weakest link...
Rabin Assumption 1: The start code cannot be cracked fast enough to locate the start of the random sequence.
Refutation 1A: The start code will need to be trivial enough that unequal computers can decypher it and start on time, thus a computer several magnitudes larger than either of these machines can likely decypher the key in an equal amount of time.
Refutation 1B: The start code would need to identify an "up-and-coming" sequence in the random stream. Therefore, either the stream needs to be partitioned (so much for a random start point), the start needs to be a frequently repeating random point (the next "A" in the stream), or the algorithm must be willing to wait for a less frequent random set (the next "ZZZ" in the stream) which would open it up to the problem from 1A.
Rabin Assumption 2: The random stream exists only in a single, linear time.
Refutation 2: Sorry if that sounded a bit trekky, but what if I set up a "reasonably" large computer that echoed the random stream with a 5 minute delay? And what if you did the same, but echoed my stream with a 5 minute delay? We could even do instantaneous echoes and use the slowdown rate of the internet to act as the time delay. I doubt this could go on infinitely, but it is entirely plausible that the net could act as a half hour repeater for all available random streams. This again opens up the problem from 1A. Refutation 2-corollary: If the streams are being slowly repeated, once the start code is decrypted by the rogue computer, it could pick up an ongoing conversation at the current point, even if it can't translate all of the previous-content.
Rabin Assumption 3: The key disappears instantly.
Refutation 3: No key disappears instantly. If a calculation was run on the start code, then there is a chance to target the code and clue in to the start sequence. Is it possible either of the communication machines can instantaneously translate the stream? Either part of the stream must remain temporarily in memory while the complete key is being gathered or the machine must be decrypting piece-by-piece. In either case, it would be possible to read some of the middle of the random stream, determine where it came from (see refutation 2) and then a bit of brute forcing could determine the start and stop of that key. Finally, the random stream (and it's location) could be determined by monitoring the source of incoming packets to the communicating computers; activity fingerprints (how quick the machine handles other requests, etc) could determine when the processing started and thus where the start sequence may have been.
Rabin Assumption 4: There is order in chaos.
Refutation 4 (not-so-sound): The only order in the disordered, random stream is that it is consistently random. As a result, it may be very difficult to carry out the high levels of math that current algorithms use; thus the computations would need to be trivial. Since (as described in my intro) the purpose of this crypt is real-time messages, it is likely it would be used for a streaming communication. Thus, a brute force attack using small random elements against small pieces of the message, piped through the simple algorithm, may well be a plausible decryption technique.
debunk away...
Si Druid
response to: The Key Vanishes: Scientist [Michael Rabin] Outlines Unbreakable Code
http://www.nytimes.com/2001/02/20/science/20CODE.h tml
As a few others have pointed out (adamwood, KFury, etc), the start code is probably the weakest link...
Rabin Assumption 1: The start code cannot be cracked fast enough to locate the start of the random sequence.
Refutation 1A: The start code will need to be trivial enough that unequal computers can decypher it and start on time, thus a computer several magnitudes larger than either of these machines can likely decypher the key in an equal amount of time.
Refutation 1B: The start code would need to identify an "up-and-coming" sequence in the random stream. Therefore, either the stream needs to be partitioned (so much for a random start point), the start needs to be a frequently repeating random point (the next "A" in the stream), or the algorithm must be willing to wait for a less frequent random set (the next "ZZZ" in the stream) which would open it up to the problem from 1A.
Rabin Assumption 2: The random stream exists only in a single, linear time.
Refutation 2: Sorry if that sounded a bit trekky, but what if I set up a "reasonably" large computer that echoed the random stream with a 5 minute delay? And what if you did the same, but echoed my stream with a 5 minute delay? We could even do instantaneous echoes and use the slowdown rate of the internet to act as the time delay. I doubt this could go on infinitely, but it is entirely plausible that the net could act as a half hour repeater for all available random streams. This again opens up the problem from 1A. Refutation 2-corollary: If the streams are being slowly repeated, once the start code is decrypted by the rogue computer, it could pick up an ongoing conversation at the current point, even if it can't translate all of the previous-content.
Rabin Assumption 3: The key disappears instantly.
Refutation 3: No key disappears instantly. If a calculation was run on the start code, then there is a chance to target the code and clue in to the start sequence. Is it possible either of the communication machines can instantaneously translate the stream? Either part of the stream must remain temporarily in memory while the complete key is being gathered or the machine must be decrypting piece-by-piece. In either case, it would be possible to read some of the middle of the random stream, determine where it came from (see refutation 2) and then a bit of brute forcing could determine the start and stop of that key. Finally, the random stream (and it's location) could be determined by monitoring the source of incoming packets to the communicating computers; activity fingerprints (how quick the machine handles other requests, etc) could determine when the processing started and thus where the start sequence may have been.
Rabin Assumption 4: There is order in chaos.
Refutation 4 (not-so-sound): The only order in the disordered, random stream is that it is consistently random. As a result, it may be very difficult to carry out the high levels of math that current algorithms use; thus the computations would need to be trivial. Since (as described in my intro) the purpose of this crypt is real-time messages, it is likely it would be used for a streaming communication. Thus, a brute force attack using small random elements against small pieces of the message, piped through the simple algorithm, may well be a plausible decryption technique.
debunk away...
Si Druid
response to: The Key Vanishes: Scientist [Michael Rabin] Outlines Unbreakable Code
http://www.nytimes.com/2001/02/20/science/20CODE.
