On October 13, 2008 , in the course of an email chain with a reader B.L. (name redacted for privacy) we received the following question. This post is placed behind a cut for minor spoilers through about Evenfall chapter 17.
Note: the conversation we had back and forth following the initial question/answer might be interesting for people to read so I included the reader’s question and my answer, and then after that included our back and forth. It’s labeled B.L. for the reader and Ais for me (if that last part wouldn’t have been, you know, self-evident or anything ^_~).
Since this conversation happened years ago I didn’t get express permission from the reader to repost this. I am hoping that it is acceptable to share this since there are no identifying details, but if you are the reader and wish for me to remove the conversation please let me know and I will do so immediately. Thank you!
Q:
How did Jeffrey break the OTP encryption on the second half of Thierry’s disk?
A:
Good question. Actually, if Thierry hadn’t subtly helped them out, it would have basically been impossible.
Jeffrey didn’t mention it but what ended up happening was that as he dug further on the disc, he’d located some small, hidden,encrypted files that at first he’d thought to be throw away, nonsense files. They were each encrypted with a different, long key in a Vigenère square and they’d seemed to just be inconsequential, incomprehensible information to distract from the two larger, more heavily encrypted files.
But when he deciphered all those he eventually figured out that mixed in with the mess was the private key needed to decipher the message. The entire thing took him awhile because he had to test different combinations of the gibberish he’d found in the throwaway files, and since he didn’t even know the length of the private key, there were a lot of combinations to test. And he didn’t even know if he was on the right track in the first place– the files could have been what he’d thought initially; just a distraction to waste the cryptanalyst’s time.
The private key included on the disk was Thierry’s own that he used in certain types of communications with Janus. The public key was not hidden information so with Owen’s help he was able to get a copy of that. Thierry had wanted the Agency to be able to get the information which is why he’d stuck his private key on there, but he hadn’t wanted it to just fall into anyone’s hands or make it too easy for regular people so he’d encrypted them and made it seem extremely likely that there was nothing of import in the files at all.
Once Jeffrey determined the private and public keys, he was able to decipher one of the files but the other was still OTP and he still needed that key. So he went back to the nonsense files and tried another number of combinations until he was able to determine where the key was hidden in there. Technically, Thierry was supposed to destroy the OTP key when he’d received it, and he had for all intensive purposes that Janus would have known– it was just that he’d left a copy on the disc for the Agency.
Once both files were eventually decrypted, Jeffrey had to combine the information between the files because they each only had half the information. That was why initially he said all he could really figure out was something big was happening in Monterrey– at that point he’d only managed to partially decrypt some of the information on the disc.
B.L.:
Thanks for the explanation. I love it when stories are realistic/well-researched. I’m a computer science major, and curious at heart, so how they broke the otp was bothering me. I figured that maybe they used the second half, that wasn’t otp’ed as the key for the first half that was, but then once they had the second half, they would have broken the first in no time at all. This makes a lot more sense.
Ais:
Yeah, actually, it wouldn’t have been possible (to my knowledge) for him to break the OTP just with will alone. Not unless they had computers capable of performing quantum mechanics which, while it would be sweet as hell, is not very likely XD Of course, Jeffrey likes to think he’s smart enough, and in a lot of ways he is, but even great intelligence can’t go against impossible mathematical odds. ;P
I know what you mean, though. To be honest, it seeeeriously bothers me if I feel like I haven’t done enough research on something. I get really nitpicky. And another part of the problem is when I’ve never dealt with something at all before writing that part– then we try to do as much research as we can to get an understanding of what is realistic, but you never know if you’re going to miss something obvious that people in the field know about that an outsider may not. So we always try to fix those mistakes if we find them.
As for the topic of cryptography– I’ve been reading this book about the history of cryptography and it’s totally fascinating… It may be something you’re interested in, if you haven’t seen it yet. It’s called The Code Book by Simon Singh. ISBN for the trade paperback is 0385495323. I highly recommend it if you’re into cryptography but haven’t had classes/learned about the history/etc.
B.L.:
I’ll look into that book, I’m actually really interested in cryptography, and I’m going to take a class on it in the near future.
As for the OTP, it would have been impossible to break, as long as the pad was sufficiently random. Not even a quantum computer can brute force a OTP, actually. Only OTP and Lamport signatures are the known encryptions that are immune to the two quantum algorithms they have postulated so far for breaking cryptography.
Ais:
Oh hey, I haven’t heard of a Lamport signature yet but I’m not done with book yet and it was just getting into quantum cryptography so I bet I’ll find out about it there.
Yeah, the other choice was that maybe the OTP key wasn’t sufficiently random, which– if it had been typed by someone and they unconsciously typed a few keys with the left hand and then the right and repeated like that, it’s possible that eventually maybe something could be figured out from it. But since there are computers available it doesn’t make sense to hand-type a key when a computer can generate it and be perfectly random. So that wasn’t even really an option for long as for how the OTPwould be broken.
Sweet, class on cryptography! If you hear anything interesting and want to tell someone about it who would also find it interesting you can always shoot an email. I was actually really lucky that I found this Code Book because cryptography is a little confusing to try to research elsewhere, since i felt like i had to know the names of things, and have an understanding of how cryptography itself works, and how they all work with each other.
B.L.:
Lamport signatures are pretty cool, they’ve very similar to OTP’s but the public key doesn’t need to be as long as the message as a OTP key does; they can also be used with hash trees to allow the same signature on more than one message (sort of).
I would be very surprised if the key was hand generated, and I assumed Janus wouldn’t be stupid enough to use a insufficiently random pad. However, computer based RNG’s aren’t very good. In fact, they suck. In some cases a person putting it in by hand would be better.
People have made some pretty interesting devices to make good random number generators: http://www.lavarnd.org/what/process.html
Ais:
Wow, that RNG device is fascinating… I never would have thought of that. I also didn’t think that computer generated RNG’s suck, so that’s good to know, lol.
Recent Comments