ec2-3-21-97-61.us-east-2.compute.amazonaws.com | ToothyWiki | ToothyWikiInternals | RecentChanges | Login | Webcomic [This] will sign text using a secret key held on the server. You can use this to keep decisions or pieces of information secret, e.g. in a game, yet later prove to someone that the decision you say you took or information you say you had is what it was at the time.
Simply use the server to sign a piece of text describing the decision or the information, and hand out the signature. Later, when you reveal the decision or information, suspicious recipients can use the server to sign it and check that the signatures match - if they do, the decision / information is the same.
Clearly, it is important that the text you sign is exactly the same as the text your recipients check; otherwise, you will be branded a cheat and a liar. The server ignores spaces, tabs and carriage returns. Everything else is significant. The example signature that follows this text includes everything between the two groups of four dashes above and below this paragraph, but not the dashes themselves. I signed the source - the text you get when you click on "Edit this page" - not the rendered text that you normally read.
Signature: f2e22eea0f8d785065a2bac4233a667a
This may well be too unwieldy to actually ever use. You lot can tell me :)
Question: If I sign the text 'paper 123456' will there always be a number x s.t. 'rock x' gives the same key? - Kazuhiko
Yes and no.
Given a piece of arbitrary text A of arbitrary length, there will always exist a piece of text B that produces the same key, and moreover there will be infinitely many pieces of text that produce the same key. (the key is 128 bits long, therefore there are 2^128 different ones, and the infinte set of all possible texts maps onto the finite set of all possible keys).
However, the server-supplied random number is never larger than 10^n where n is an integer greater than 5 and less than 9 that I don't remember. This is less than 2^128, so there will not necessarily be a server-supplied number x such that there exists a number y that could plausibly have been supplied by the server, with "paper x" and "rock y" producing the same signature.
Not really. Few people have the computing power to do a keyspace search of that magnitude, and if any do I don't see them using it to break a game on ToothyWiki. Even for them, there is a difference between finding a piece of text that maps to the same one of (2^128) possible keys as another piece of text, and finding a piece of text that says what they want it to in a way the original author could plausibly have said it and maps to the same one of (2^128) possible keys as another piece of text (which is partly why I suggest appending meaningful english text on a random subject to pad short pieces of predictable text you may wish to sign).
If anyone actually found an algorithm for producing bit-sequences with the same key as any specified bit-sequence then they'd rapidly become famous in cryptographic circles.
Does that help? I'll dig around for links on the subject tonight, if anyone's interested.
That's fine. Just as long as x can't be calculated... - Kazuhiko
Finding a way to calculate x which is faster than testing each possible x is known as breaking the signature algorithm :) MD5 (which is what the server uses) has been heavily cryptanalyzed, but hasn't been broken yet.
Although one could make use of the birthday problem to make the system easier to crack by several orders of magnitude. Actually, it's not the birthday problem at all, but a similar idea. Mike Bond and co-conspirators used the idea to break an expensive bank security computer system. Basically, one would set up a large number of "rock ..." strings, and take the hash of all of them. Then create a FPGA (read: programmable hardware) that contains all of the hashes, and is capable of comparing a value to all of those hashes at once. Then create some system that generates a stream of hashes of strings like "paper ...", and pass them all to the FPGA. Therefore, you are comparing your generated stream to many possible alternatives at the same speed as you would otherwise compare the same stream to just one alternative on a conventional computer. It's fun, cheap, and allows poorly-funded people to break expensive security systems. Oh, and Bruce Schneier is of the opinion that MD5 is showing cracks. --Admiral
...but the signature server isn't just a straight MD5 hash of the input, it adds salt to it - a few K of random bytes hardwired into the script. Any FPGA you make to find collisions would have to include the salt, or the signatures generated by the server would be different to those generated by your model. OTOH, this has a downside - if the host is compromised, the salt would have to be changed, rendering past signatures uncheckable. - MoonShadow
Technically it's not really a salt if it doesn't change - it's merely a hash function that can only be generated by your server. However, it doesn't change the attack at all - the FPGA doesn't need to know anything about the hash function at all - all it does is allow you to perform x + y hashes (which could be done by asking the signature server), and effectively check x * y possibilities. This doubles the effective number of entropy bits that can be searched by brute force, making breaking the system as hard as breaking a hash with 65 bits rather than a hash with 128 bits. Admittedly this is still quite hard. --Admiral
Oh, additionally, can't the server detect when it is being attacked in this way? Not a perfect defence by any means, you could trickle the requests in - but for a low traffic server like this one, it would be a good first line of defence ;) --Vitenka
Certainly - and that is the benefit of having that "salt" kept secret. --Admiral
Is there a reason you couldn't keep the old one around too, with big warnings saying "WARNING: COMPROMISED - Use only for checking old signatures! Go [wherever] to sign new things"? --AlexChurchill
Admiral - throwing n computers at a problem to solve it in time 1 instead of n isn't actually a break - you're just trading hardware for time. Of course, that's the step between theory and practice. It's a practical attack. MoonShadow - hiding the salt doesn't help, you just generate the things you are testing against by throwing the 'rock...' strings at the server, it adds salt and returns the hash, which you then add to your table. Things get harder only because people are themselves adding salt rather than having raw 'rock' as their move. Alex - yes, but only if the hash is known to be compromised. You could regularly rotate it, or rotate it after so many uses or something like that - but right now that wouldn't help. Of course, anyone throwing an fpga at rock-paper-scissors probably deserves to win. --Vitenka
Okay, how about not using an FPGA at all. Create that same load of hashes, and put them all in a hash table in a normal computer program, so you have constant-time lookup. Then throw the stream of hashes at it, and wait for one to collide. With a bog-standard modern computer with 1GB of RAM, you could reduce a 64-bit hash to an afternoon's computing, or a 128-bit hash to merely the life of the universe, rather than a thousand million times the life of the universe. It is sort of a break - but very specifically a chosen-plaintext attack, assuming one can run the hash function on that chosen-plaintext. --Admiral
Having read a precis of the paper I presume you are referring to: Ouch. No actual demonstrated breaks yet, but a pretty good chance of getting a collision to any given hash. I'm a bit lost in recent crypto - will this break SHA1? And if not, surely it's pretty trivial to replace MD5 hashes with SHA1 hashes throughout? I notice that a lot of open-source stuff has been defaulting to SHA1 over MD5 for a while now. --Vitenka
If you're referring to the algorithm I specified for finding two strings with the same hash, then it is independent of the hash function. However, note that finding a string with the same hash as another specified one is still difficult. --Admiral
I meant the BruceSchneier comment. Finding two strings which happen to generate a collision is always going to take ... damn, I've forgotten the folrmula. It's the one for proving that having two kids in a class of 30 having the same birthday is almost a dead cert. It relies only upon being able to do a number of tests approaching the ratio of hash size to plaintext size. You can make the number of tests that need to run go up at a rate of log rate at which you increase the size of the hash. That assumes constant time for comparing the outputs, which isn't quite fair, even on modern hardware. --Vitenka
Firstly - BruceSchneier thinks MD5 is showing cracks. This has nothing to do with SHA1. Secondly, the algorithm above will apply to SHA1 just as easily as MD5. Thirdly, this problem is slightly different from the birthday problem, namely that we want to include specific information in the two chosen plaintexts - this means we are trying to find a collision between two sets of hashes, rather than finding a collision inside a single set of hashes. Fourthly, hash tables have constant time access characteristics. If all the hashes generated so far fit in memory, they can be checked for in constant time. In fact, that even works when the hashes have to spill over onto secondary storage. --Admiral
I had an argument that hash tables only lookup in constant time in the (near) perfect case - but then realised that if your hash values didn't fit that case then you've found a statistical attack anyway which is better. It's good to know that SHA1 doesn't inherit that flaw in MD5, since in most situations you can rip it out. And the problem devovles to the birthday problem - you just first ask everyone not born in August to leave the room and it is equivalent again. Of course, since we are now using a sdmaller set of plaintexts, the chances of a collision existing go down. Which brings up a point. Is it better to use truly random salt in the stuff you are hashing - since if you don't then you have a good chance that no collision exists, but you have a better chance of just getting guessed. --Vitenka
People would need to keep the salt around so they could verify the hash again. Which is equivalent to having people add random stuff to text they submit, which is suggested at the top of the page. - MoonShadow
That wasn't quite what I meant. If someone can post a reasonable piece of text which verifies as having the hash I just posted, then they can claim to be me. If they have the ability to add random junk to something and still claim it is reasonable, then that gives them a bigger search space to choose a message from. So it is more likely to say what they want. But if they have to have plaintext then they know there is plaintext there, and so have a better chance of stumbling across what I actually wrote. How do I best balance these two risks? If I am on the site when this hypothetical attacker strikes, I can always counter with "No, I didn't write that, you're not me". Mind you, being able to prove that a collision exists would show that at least one of the two of us is an attacker, then our messages would have to be compared on face value, as though neither had been signed. Which is no worse than not signing. --Vitenka (So, um, the risk balance is between authenticity and uniquness, I guess)
Hmmm - may as well test the security. Military grade secrets exist under the hash 4f4beb15bba34e1ed61cb35c421d383e - And to give you a hint, it contains only english words and simple punctuation - and I'll hint further that it includes my normal signature. --Vitenka
Update: MD5 has been successfully cryptanalysed. Will add a more secure alternative as soon as I know what's secure these days. - MoonShadow
Really? When you find the reference, would you mind also adding it to the WikiPedia: MD5 article? Thanks. -- DavidCary?
If you scroll down, you'll find that that article already has a section at the bottom with links to papers on MD5 collisions/cryptanalysis. - MoonShadow
The birthday attack does not depend on which hash function you use. So you either need to design a protocol that blocks any possible attempt at a birthday attack,or choose a hash with twice as many bits as you would otherwise need. (Since I suspect MD5 already has more than twice as many bits as we need for our silly little toothycat games, we don't need to change anything.) -- DavidCary?
Indeed. However, if you read the conversation above, you will find that it was started by Admiral specifically talking about a massively parallel device for finding MD5 collisions. -MoonShadow
![[Home]](/img/text_logo.jpg){kind=logo}
ToothyWikiInternals/SignatureServer