Venona not all decrypted?
ggr at qualcomm.com
Tue Oct 4 10:13:32 PDT 2005
At 16:20 2005-10-03 -0400, R.A. Hettinga wrote:
>I just heard that the Venona intercepts haven't all been decrypted, and
>that the reason for that was there "wasn't enough budget to do so".
>Is that "not enough budget" to apply the one-time pads they already have,
>or is that the once-and-futile exercise of "decrypting" ciphertext with no
>one-time pad to go with it?
Here's my understanding of how Venona worked, and why budget would be
a problem. I could be completely off base, though.
The OTPs were only very occasionally misused, by being used more than
once. So the breaks occurred when two separate messages, or possibly
fragments of messages, were combined in such a way as to cancel out
the OTP, then the resulting running-key cipher was solved to yield
the two messages. I don't think that the NSA had access to the pads
themselves, except after having recovered the messages (and hence the
pad for those messages). So there really isn't likelihood that that
pad would be reused even more times.
To detect that a pad has been reused, you basically have to line up
two ciphertexts at the right places, combine them appropriately, and
run a statistical test on the result to see if it shows significant
bias. This is an O(n^2.m) problem, where n is the number of units to
be tested (maybe whole messages, maybe pages of OTP, maybe at the
character level? Who knows?) and m represents enough text to reliably
detect a collision. There was a very large amount of intercepted
data, and it's presumably all stored on tapes somewhere, so that n^2
factor probably involves actually mounting tapes and stuff.
But in a way, you're right; it should, with today's technology, be
possible to just read all the tapes once onto a big RAID, and set the
cluster to work for a year or two.
Greg Rose INTERNET: ggr at qualcomm.com
Qualcomm Incorporated VOICE: +1-858-651-5733 FAX: +1-858-651-5766
5775 Morehouse Drive http://people.qualcomm.com/ggr/
San Diego, CA 92121 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
More information about the cypherpunks-legacy