3 ms·

1. It's assumed that the seed you get from /dev/urandom is unguessable. This is a very solid assumption to make. The reason why it's a good idea to use an HMAC

by antirez 11y ago

1. It's assumed that the seed you get from /dev/urandom is unguessable. This is a very solid assumption to make. The reason why it's a good idea to use an HMAC is entirely different and is the following classes of attacks, not a matter of costs of bruteforcing (which is impossible becase of the search space, without having some clue of the content or state of /dev/urandom). For example, for an error the code could be written to SHA1(seed || counter). In this case you can "re-open" the hash function and perform an "length extension attack", so you add "0" at the end and successfully predicted one of the successive IDs. HMACs are constructs used to make sure the secret and plaintex is mixed in a more cryptographic robust way, basically. 2) If you don't trust /dev/urandom to seed the generator, you have no reasons to trust that /dev/urandom cannot be predicted by observing some part of the old stream of bytes. More information about the attack I described are available here: https://en.wikipedia.org/wiki/Length_extension_attack https://en.wikipedia.org/wiki/Length_extension_attack

mrb 11y ago
The construct described in your blog, H(counter+seed), is not vulnerable to length extension attacks, so you gain nothing by using an HMAC here. The only thing I thought you could be theoretically referring to when you wrote "very hard to predict" was bruteforcing, so I talked about bruteforcing on a theoretical level. I agree of course that a 160-bit seed from urandom can be trusted and is not bruteforceable in practice.
- antirez 11y ago
  To make things simpler for our discussion, I made as example the length extension attack, but message||secret has other more subtle issues (there is extensive documentation about it and many papers detailing the attacks. A more robust way that is still weak compared to HMACs is secret||message||secret). So you gain security by using an HMAC. Given all the above you may want to update the sentence "The author says SHA1_HMAC would make IDs "very hard" to predict compared to SHA1, but this is not true at all", for the sake of other readers not following the whole discussion.
  - mrb 11y ago
    Again, your H(counter+seed) solution for generating unique IDs is perfectly fine. This is clean, neat and fast. There are no subtle issues whatsoever. An HMAC will not give you any extra security in this case. (The issues with H(message+secret) only exist when the attacker has some control on "message", but he does not in your case --I am familiar with this, I do crypto reviews for a living.) I cannot update my comment (HN only lets you edit posts < 2 hours old), but I would not want to update it anyway since what I say is true :) However I think you should edit your blog post and mention that the order of concatenation of the counter and seed is important. If you want say something along the lines of "HMAC is traditionally the best practice but in this case H(counter+seed) is fine".

by antirez 11y ago

mrb 11y ago

The construct described in your blog, H(counter+seed), is not vulnerable to length extension attacks, so you gain nothing by using an HMAC here. The only thing I thought you could be theoretically referring to when you wrote "very hard to predict" was bruteforcing, so I talked about bruteforcing on a theoretical level. I agree of course that a 160-bit seed from urandom can be trusted and is not bruteforceable in practice.

antirez 11y ago
To make things simpler for our discussion, I made as example the length extension attack, but message||secret has other more subtle issues (there is extensive documentation about it and many papers detailing the attacks. A more robust way that is still weak compared to HMACs is secret||message||secret). So you gain security by using an HMAC. Given all the above you may want to update the sentence "The author says SHA1_HMAC would make IDs "very hard" to predict compared to SHA1, but this is not true at all", for the sake of other readers not following the whole discussion.
- mrb 11y ago
  Again, your H(counter+seed) solution for generating unique IDs is perfectly fine. This is clean, neat and fast. There are no subtle issues whatsoever. An HMAC will not give you any extra security in this case. (The issues with H(message+secret) only exist when the attacker has some control on "message", but he does not in your case --I am familiar with this, I do crypto reviews for a living.) I cannot update my comment (HN only lets you edit posts < 2 hours old), but I would not want to update it anyway since what I say is true :) However I think you should edit your blog post and mention that the order of concatenation of the counter and seed is important. If you want say something along the lines of "HMAC is traditionally the best practice but in this case H(counter+seed) is fine".