Schneier on Security
A blog covering security and security technology.
« Cost/Benefit of Terrorism Security |
| Friday Squid Blogging: The Mystery of Humboldt Squid Beaks »
September 12, 2008
The Doghouse: Tornado Plus Encrypted USB Drive
Don't buy this:
My first discussion was with a sales guy. I asked about the encryption method. He didn't know. I asked about how the key was protected. Again, no idea. I began to suspect that this was not the person I needed to speak with, and I asked for a "technical" person. After a short wait, another sales guy got on the phone. He knew a little more. For example, the encryption method is to XOR the key with the data. Those of you in the security profession know my reaction to this news. For those of you still coming up to speed, XORing a key with data to encrypt sensitive information is bad. Very bad.
EDITED TO ADD (9/13): In the comment thread, there's a lot of talk about one-time pads. This is something I wrote on the topic in 2002:
So, let me summarize. One-time pads are useless for all but very specialized applications, primarily historical and non-computer. And almost any system that uses a one-time pad is insecure. It will claim to use a one-time pad, but actually use a two-time pad (oops). Or it will claim to use a one-time pad, but actually use a stream cipher. Or it will use a one-time pad, but won't deal with message re-synchronization and re-transmission attacks. Or it will ignore message authentication, and be susceptible to bit-flipping attacks and the like. Or it will fall prey to keystream reuse attacks. Etc., etc., etc.
Posted on September 12, 2008 at 12:05 PM
• 55 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
Well, not if the key is a unique one time pad... Maybe the drive has an LCD display that you memorize the pad from before encrypting, which you reenter to decrypt. Simple, right? You just have to be able to easily memorize a billion bit string...
oh come on. which encryption technique doesn't use xor somewhere? Ignorance is still ignorance, even after a phone call to someone else ignorant.
Correct me if I'm wrong, but I don't think the problem is with using XOR. The problem is using a (relatively) short number of bits over and over and over against your sensitive data. Wouldn't that allow you to look for patterns and then determine the key? Is Grahame's comment going over my head?
You have it about right, Kevin.
XOR as an encryption algorithm only works if you use a one-time pad that has the exact length of your message. I really doubt that's the case here.
Forgive my ignorance, but what's the problem with this? I really don't know anything about encryption, so I don't understand why this is bad.
Thanks in advance
You didn't read the link, did 'ya? It's an RFID that transmits, in the clear, the key. It's seems "unlikely" that it's transmitting gigs to the drive; and anyhow, there is no protection on the key itself, so an RFID reader could surreptitiously pick that up, as well.
What's the problem. See Joshua's statement. It's metaphorically the same as adding a number to every character as an encryption method - it wouldn't take a very sophisticated investigator to break that!
ROT13 is not your friend!
Ahhh... XOR "encryption". I remember when I was about 14 I had the Atari ST version of the game "Elite". I reverse-engineered the format of its saved-game files, which were 256 bytes long. The developers had "encrypted" the file by XORing each byte with its offset in the file (i.e. the "key" was 0,1,2,3,...255), which probably would have taken me longer to figure out if the last few bytes of the plaintext hadn't been zeros. Far from the greatest feat of cryptanalysis ever performed, but I remember being pretty pleased with myself at the time :-)
XORing the data just means that every place where the key is a "1" the encrypted data's bit gets flipped, and where there's a "0" it gets left alone.
This is the sort of encryption that you'd write in 5 minutes if you just needed to hide something trivial from casual observation.
It's trivial to break. The easy case: most filesystems will have, somewhere in them, a file that has a lot of 0s or 1s. Find a place where there are repeating patterns of bits, and you probably just found a place where the original (cleartext) was all zeros or ones, and you can deduce the key trivially (you get it down to two patterns, just try them both).
The other possibility is that you have a case of "known plaintext". For instance, perhaps you know that Windows XP always writes a certain bit pattern to the boot sector, and you know the owner uses XP (if not, perhaps you only have to try a few different OSs signature boot sector). Read the encrypted boot sector, XOR it against the known plaintext, and you have the key. Takes a fraction of a second.
Oops, the previous long message was by me, FOR Matt. Sorry.
Thanks all for the explanations.
If rot13 is so trivial, well, just use a large number of rounds!
It doesn't sound like the reviewer spoke to anyone authoritative at the company that makes the drives. Most companies' support stinks - even the major manufacturers - Apple, HP, etc can't get it right when supporting consumer-grade customers. It's wrong, but doesn't make it insecure.
For all we know, "Anthony" could be a lowly paid support technician. The reviewer could also have come off as a basket-case (who's got two weeks of free time to make calls to a vendor like this anyways??) and was ignored by the vendor.
As long as you can guess even a short amount of the plain text, breaking xor is trivial. On a flash drive, a Microsoft Word document will contain the string "Microsoft Word Document" somewhere near the end. Guess the password is 8 characters in length. Xor "Microsof" with "t Word D". Now iterate through the whole USB key, Xoring each 8-bytes strings with the subsequent 8-bytes string. When you have a match for the expected pair, you xor the first 8-bytes with "Microsof" and presto, you have the key. It's trivially easy to automate this for all possible lengths of passwords.
Simple question about XORing: If the key is longer than the message, how do you crack the encryption?
Little did that company sales rep realize it was Bruce was on the phone.
Bruce, why were you speaking with sales? Like shooting fish in a barrel? Did you ever reach anyone technical?
I should follow up to my post and state that this drive probably is crap, but instead of being some creepy guy hassling support for 2 weeks, he should just get a RFID reader, and show how vulnerable this drive actually is.
If the key is perfectly randomly generated, you don't. That would be a One Time Pad, and cannot be broken (theoretically, a given ciphertext could map to any random plaintext). Of course, that is assuming you don't use the key for anything other than that one message, which would break the conditions for a OTP. If the source of the key lacks sufficient entropy you could attack there. Of course, in the case of this device it seems possible that the key is being transmitted via RFID in the clear, so snooping that would be an easy way to "crack" the encryption.
The excerpt was written by Tom Olzak of TechRepublic.
I feel the need to add that the reason XOR is scoffed at despite mathematically provable unbreakability is because you need the key to be equal or longer than the length of the message, and transmitted safely in private. If you can transmit the key safely without interception, you can just transmit the data via the same channel instead.
If you have a great random number generator that you can effectively seed, you can use that as a source for a key of the same length as the plain text. Then Xor starts making sense again as an encryption algorithm. Of course then you have a stream cipher... In fact this is exactly what RC4 does, all the difficulty being in trying to effectively use the key bits and generate the most random keystream possible. The key re-use weakness is still there however.
If only there was some way to use a satellite surveillance gait analysis biometric to improve this system...hmmn?
It's a lot easier to just say that XOR is not an encryption method at all. Things like "xor against a trivial calculated key", "xor with a repeating key", "xor with a cryptographically secure stream of data generated from a key", or "xor with a one time pad" are encryption methods. The XOR is just one of the operations. Of the above, note that the first and second are suitable for preventing your kid sister from reading your mail, and the third and fourth are potentially secure but have lots of caveats.
I think the article is dead on about evaluating security products. Encryption designed by people who understand it also understand the importance of communicating this information. If someone says "it uses AES", I'm still not clear if they handle keys properly, but if someone says it uses "RFID Data Encryption", I'm very clear that they don't know what they are talking about.
Ooops, thanks. For some reason I missed the obvious; Bruce often doesn't write much on his blog, especially on fridays.
Where's the squid?
Weekend here I come.
What if the entire drive came already encrypted with AES, and the user merely changed the password? Would this be secure?
@Matt: "XORing the data just means that every place where the key is a "1" the encrypted data's bit gets flipped, and where there's a "0" it gets left alone."
Sorry, but wouldn't that just leave you with a string of 0s? Given key and message block of key length these are compared bit by bit. If key bit = message bit it's flipped, if not it's left. xoring again with the key will return the original message.
It wasn't Bruce on the phone, it was Tom Olzak. (You know, the guy who wrote the article?)
And frankly, if you're a salesman selling a product that offers "encryption" as one of its main selling points, you have to be prepared to tell people how it works. If you aren't able to tell them that, they will rightly consign your product to the doghouse.
...But that's not the main reason this product belongs in the doghouse. This product belongs in the doghouse because it uses "encryption" that any 5-year-old kids could break. The security value of this product is probably negative (start with almost zero, and subtract a large number for the false and misleading sense of security that naive buyers might get from its advertising).
If you want to see why you shouldn't use XOR to encrypt your data, you should read "Applied Cryptography". Using XOR alone as your encryption scheme leaves way too many paths for cryptanalysis (and eventual decryption) of your data.
A linear feedback shift register generating a PN sequence can be arbitrarily large, and for key generation it can be started at any random phase and be iterated until it produces a sequence equal in length to the message.
A LFSR of 1024 bits would have a period of 10 to the 308th power, which is a lot of phase space.
I think XOR is fine! After all, you do not need to remember any encryption key with it, recovering the data is so trivial, you can even do it manually!
So the author of this blog post, who as far as I can tell has never seen the drive or taken one apart, has decided that based on conversations from obviously clueless helldesk staffers, the drive couldn't possibly secure. Now it may well be that the RFID tag transmits the encryption key in the clear and that key is XORed repeatedly with the data to decrypt the drive. On the other hand, maybe the drive is encrypted using elliptic key cryptography with a randomly generated key stored in hardened, tamper resistant packaging. Maybe the RFID tag is hardened also and talks to the drive using a zero knowledge protocol to prove its authenticity without leaking any information. Only after that happens does the drive make the data available. We don't really know.
What we do know is that the blog author, who scorns others for making snap judgments about the product, didn't seem to have any more knowledge than they did before he rendered his verdict.
@Grahame and those who followed.
Simple XOR is fine but to have a good key you have to have a really really really (notice 3 times) long random pattern .. which is a rather problematic .. because
a) it will have poor entropy after the block length
b) a long long long key will be impractical.
that's why Bruce get paid big bucks to design 2/3/4 fish-dinners
Xor is generally the last step of all encryption algorithms -- but that's like saying digial electronics is 50% zero's.
(actually good encryption should result in that!)
LFSR is a generic technique (fairly robust) of mixing data with a key .. though modern encryption algorithms use more complex structures to mix data and key.
Unless it's backed by a decent encryption algorithm that protects against basic attempts -- it's a waste of time -- Maybe it's a bad salesman, but most likely a bad design.
@R3ACTOR -- no you are totally wrong
@R3ACT0R: "We don't really know."
Right. So it's presumed insecure, and the advice is "don't buy". What's the problem?
This isn't a criminal trial. Companies selling security products don't automatically get the benefit of the doubt. If they are unable to provide a potential customer with a single reason to believe that their product provides security, and if they fail or refuse to describe even the cryptographic algorithms they use, let alone other security-critical details, then they go in the doghouse.
"Maybe it uses elliptic key cryptography"
Sure. "Maybe" it comes with a free donut. "Maybe" it doubles as a flying car that gets 100mpg.
If it does, the burden lies on the company to mention it. What kind of dumb-ass customer does the vendor's job for them by assuming the product is perfect unless proven otherwise?
Things like "xor against a trivial calculated key", "xor with a repeating key", "xor with a cryptographically secure stream of data generated from a key", or "xor with a one time pad" are encryption methods. The XOR is just one of the operations. Of the above, note that the first and second are suitable for preventing your kid sister from reading your mail, and the third and fourth are potentially secure but have lots of caveats.
The caveats with the third include securely communicating both the key and the algorithm used. In most cases you might as well use this method to communicate the message you want to send.
With the fourth you need a method of securely communicating the one time pad. Since this one time pad needs to be at least as long as your message you'd be better off sending the message using whatever method you intended for sending the one time pad.
Several comments here really miss the only thing that saves One Time Pad. They say, essentially, that if you have a way of sending the pad securely then you should just send the message.
This neglects two cases.
*) If the message path from you to me is secure but the path from me to you is not, then you can send me a one-time-pad, and I can use it to encrypt my message to you over the otherwise unsecured channel.
*) We can meet in person and exchange tons and tons of one-time-pad bits. Say, a stack of DVDs. Months later, when we are thousands of miles apart, we can exchange messages over an unsecured link using those pads.
OTP may or may not be useful -- but the straw man argument that you could have sent the message when you exchanged the pad does not extend to invalidating all uses of OTP.
A couple of people posting mention the long lengths of bit streams generated by LFSR's (Linear Feedback Shift Registers).
"A LFSR of 1024 bits would have a period of 10 to the 308th power, which is a lot of phase space."
Are very missleading. Most LSFR's are trivialy broken with a section of their output that is between 2 and 3 times the length of the shift register. Which if you think about it makes them only marginaly more secure than a counter of the same length....
And LSFRs have another property that is not cryptographicaly helpfull. If you take a section of the output and XOR it with another section of output, it results in another section of it's output. This property is highly desirable for other things like generating AWGN and for testing amplifier response.
There for the only times you should use an LSFR as a stream generator in communications is either when sending test traffic to work out your BER or to use as a method of spreading your signal spectrum to stay inside a power mask (as used in CCITT modems etc).
You can also use it in cryptography where you might otherwise use a counter. That is when it is being fed into a nonlinear network of suitable crypto strength like a block cipher.
The design of LSFR's is usually a case of look it up in a table to get the taps. Unfortunatly most tables only give sparse tap info as it is assumed you want an efficient implementation as a random number generator for running simulations not anything to do with crypto.
The design of good Non Linear Feedback Shift Registers is an arcane art practiced in Europe more than the U.S. Historicaly this has been by the military or other branches of the security services. Therefor not much is known about good design practice.
This is considered (in Europe) to be a bit of a problem as stream ciphers do have some advantages over block ciphers which is why they where included in the EU NESSIE Project.
However if you care to look up the NESSIE project results you will find that they did not get any stream generators that where considered suitable...
This failier resulted in a new EU project eSTREAM to try and resolve the issue,
One stream cipher SNOW 1.0 was improved as SNOW 2.0 and was taken forward into eSTREAM as a refrence to judge speed.
There's another use case for OTPs.
Suppose that Alice and Bob have a full-duplex communications channel. However, the higher level protocol running over their channel operates in half-duplex mode. We can call this situation "three-quarters duplex" (*).
(* We can extend the "three-quarters duplex" concept to the case where the higher level protocol is only approximately half-duplex.)
Further, suppose that the information Alice and Bob are communicating over this "three-quarters duplex" channel is real-time data. Particularly, suppose that it's sensitve to latency. And also, suppose that our preferred response to channel noise is to drop part of the stream. That is, no retransmission at the lower layers of the protocol.
An example of this situation is a two-way, real time voice communications--where, usually, only one person talks at a time.
Now, if both sides have good sources of entropy, then they can efficiently use the full-duplex capababilty of the lower communications layer.
Alice can generate a one-time key. She can use a delay-expensive computational procedure to encrypt the key for transmission to Bob and Bob can use a delay-expensive computational procedure to decrypt the one-time key. Bob buffers the key for later use. Then, when Bob has real-time data to transmit, he can use a delay-inexpensive computation (an XOR!) for encryptation of that data. And Alice can also use a delay-inexpensive computation (just another XOR!) to recover Bob's real-time stream.
The other half of the circuit (Alice's real-time data for Bob) works the same way.
"Sorry, but wouldn't that just leave you with a string of 0s?"
No. 0 xor 0 = 0, 0 xor 1 = 1, 1 xor 0 = 1, 1 xor 1 = 0.
"Given key and message block of key length these are compared bit by bit. If key bit = message bit it's flipped, if not it's left."
That's not XOR. It can be expressed as a Boolean logic function, but it still isn't XOR. And off the top of my head, I'm not sure its invertible by applying the function again with the same key.
The boolean expression for "If key bit = message bit it's flipped, if not it's left" is ~key.
No, it isn't invertible to recover the message, since the output doesn't depend on the message...
Too many companies these days seem to make erroneous claims of one time keys etc. Found a nice short article which ripped apart one such product. Think the author is British, not too technical, but very funny.
No offense Bruce, but you do not have a Ph.D. degree.
ljklkjsdf must work for Aluratek!!
The biggest and most obvious problem with OTPs are that they are just as awkward as the original file. All you are doing is increasing responsibility for maintaining confidentiality of the plain text, with the responsibility for maintaining confidentiality of BOTH the XOR'd plain text AND the OTP. And they are both the same size. Ugh. Now where do you hide the OTP? And if you can pass the OTP to the other party without detection, THEN WHY CAN'T YOU JUST PASS THE ORIGINAL FILE to the other party?
LFSRs are good for a lot of things, but you need to remember that a maximal-length LFSR sequence includes all (but one) possible strings the length of a shift register. Ths, a 1024-bit LFSR will contain a string of 1024 ones somewhere, and a string of 1023 zeros (or vice versa). If you are just XORing with your secret message, how sure are you that the "break in the clouds (and there are of course many more smaller breaks) won't line up with the crucial bits of your message?
Don't think about OTP as a panacea. Good physical random generator is impossible without additional strong numeric methods. I believe that bruteforce on physics is also possible.
Anybody knows good random theory?
Using random xor with data U must remember about probability:
So, probability to broke of real OTP is not 0
@MikeA: "break in the clouds"
The attacker will have no clue whether the ciphertext he sees is actually produced by XORing the plaintext with a series of zeroes or by XORing a completely different text with a random sequence so that this particular ciphertext is created.
Per your assumption, the latter is sure to happen as well.
@MildredThermite: "And if you can pass the OTP to the other party without detection, THEN WHY CAN'T YOU JUST PASS THE ORIGINAL FILE to the other party?"
The answer is that you can use different channels for both as they have different requirements:
You might have messages that are too urgent to be sent by secure courier. But, when setting up a communications line, you would probably be able to do this far enough in advance so that sending the OTPs by courier is possible.
For maximum security, I encrypt anything I write (including this comment) in ROT13. Twice.
And sometimes, to feel even safer, I even XOR it with 0x0000000000.
Are you hear, that OTP random blocks had generated before we know what we can say. For example, the OTP random blocks in the submarine would be loaded onboard in the port. This is well-known reality.
Bruce, do you think systems like Opie and S/Key are insecure?
I didn't mention the possible uses of OTP (the afforementioned "lots of pads on DVDs") because really, the possible use is so limited that it's really a solved problem in much simpler ways.
Communicating over an untrusted channel? Use a Public Key Cryptosystem, RSA/ECC/etc. No need for the DVD swap, which is more complicated (you'd need an agreed upon protocol for which offset to use for any given use or transfer the starting offset each use, and you'd need to keep the disks secret...suitable for a hobby, but not real security).
As for the mentioned "keeping codes on a submarine" example, it assumes the codes are kept secret. At that point, the only practical advantage a OTP has over most other cryptosystems is it can be decrypted by hand.
OTP may have a very narrow use in low-bandwidth channels where you transmit pads ahead of time and want to retain the ability to decode them by hand, but in Bruce's words "They replace a cryptographic problem that we know a lot about solving -- how to design secure algorithms -- with an implementation problem we have very little hope of solving."
Unless cryptographic breakthroughs destroy current protocols, One Time Pads really don't solve any problems that need solving.
OTP is suitable in the circumstance where the parties are connected by at least two channels, one high-bandwidth and secure (but possibly with a very high latency) and one low-latency and insecure (with bandwidth sufficient to messaging). In the early 1960s I used a system where the secure channel was an airplane full of reels of punched paper tape accompanied by couriers, and the insecure channel was a radioteletype link between TaiPei and Fort Meade.
NSA operated a random stream generator that included a physical component (probably a Geiger counter but I did not Need To Know) and punched pairs of tapes by the truckload. The message was XORed with the key for encryption and decryption.
"At that point, the only practical advantage a OTP has over most other cryptosystems is it can be decrypted by hand."
Which is probably it's second advantage.
The biggest advantage is short message strength.
A dirty little secret of a lot of ciphers is transposition. Which means in practice that there is a minimum message length that needs to be sent to get the required level of security.
Which has a consiquence of also needing good random fill upto whatever the minimum size is and a reliable method of detecting what is fill and what is message, both of which can be problematic in real systems.
A number of early secure teletype applications suffered from the problem that when used to send user response key press by key press effectivly they became a simple substitution cipher. Similar problems still exist in some applications.
Oh and by the way OTPs used for military type communications are not truly random for a whole host of good reasons (ie run length limiting and predictable pattern removal).
Perhaps the most frequent use I have seen OTPs used for is "Engineering Order Wire" (EOW) communications.
The Military still use real OTP pads for emergancy use such as to transfer Keymat to bootstrap other crypto systems.
An example being, you "drop" a sigs tech into a hostile area they carry a very limited amount of OTP material with them but no keymat for the cipher equipment they also carry. Which if they "cream in" is therefore usless if recovered by the opposition (other than as a door stop).
If the sig tech is captured their other security checks will show forced use. If the checks pass you then send the real keymat under the OTP to "fill" (be loaded into) the cipher equipment which is normaly a one way operation (ie no way to read it out again).
A match destroys the used OTP sheets and the sig tech should not (for their sake if captured) have been able to memorize it so it is effectivly unknown from that point on.
For this and many other reasons OTPs are just to dam usefull to ever stop being used in anger.
Oh and if you want to make your own OTP you do not need much a stout beer glass with four or five dice in it with a beer mat over the top to make a "shaker" is usually more than sufficiently random to use. And large size Rizzler papers and an old manual typewriter to produce the actual pads. As an excercise with students I have found they can usually produce a hundred char pad in about half an hour with only a little practice.
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.