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. Greg Rose INTERNET: ggr@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