So I am currently working on some code that does fingerprint hardening.
There are two main objectives:
1) To reduce the size of the fingerprint that a user needs to print on a
business card etc. while preserving the same work factor.
2) To discourage the use of 'vanity fingerprints' such as
'PHBIS-MEEEE-2QHE8-2IIW9-3IIS2' which look really kewl but are actually a
major security hole as they encourage people to only check the signature
part that is easily memorized.
3) To improve the level of security achieved in the system in practice by
reducing the number of characters that need to be checked to preserve
strength.
Some observations:
1) Even the slowest modern machine can produce tens of thousands of hashes
a second, i.e. 2^12.
2) The difference in speed between the slowest modern machines and the
fastest isn't really very much when you compare single cores.
3) Searching for fingerprints is a trivial parallelizable problem and can
be performed by multiple cores. Since I have 2000+ cores in my GPU, I can
search for fingerprints at a very fast rate indeed.
4) Generating DH/ECDH public key pairs takes a small amount of time but
generating RSA keypairs causes a noticeable delay if performed repeatedly.
[The delay for ordinary keygen is also noticeable without a properly
threaded UI but no amount of threading hides hardening]
5) Regardless of the size of the machine, diminishing returns are hit after
an hour. Running for a day only reduces the fingerprint by two more
characters and a month only gives another two. To reduce the fingerprint by
five characters takes half a year.
6) This is not the type of program we want running on Amazon compute cloud
unless the fingerprint variation only involves the private key.
7) Since we look set for Base32 output, it makes sense to limit hardening
to increments of 5 bits with some minimum floor.
8) Five Base32 characters is 125 bits which is in the ballpark for a 2^128
work factor. Four groups of five characters, 20 in all is probably as long
a string as we can expect people to check. That requires an expected 15
million trials, not allowing for whatever overhead the control info
requires.
The last part means that if you want to harden RSA fingerprints, you really
have to design the fingerprint in such a fashion that you can generate the
key once and introduce some sort of salt to let you vary it. This is a
problem with my current code as even running it on an overclocked machine
with 12 processing threads, hardening to reduce the fingerprint size of RSA
keys without a salt is just not feasible.
I do not have code for the CFRG ECC algs yet so I am working on DH keys as
dummies.
The best way to organize the UI seems to be to have the user estimate how
much time they want to put into hardening the key and then give them
continuous feedback on the best fingerprint found so far. It is fairly easy
to work out how long it is likely to take to cut 25, 30, 35... bits off the
fingerprint length.
Conclusion, hardening is worth having, it is not just a matter of
convenience, it makes the system more robust. But if it is supported, some
form of salting mechanism is essential.
_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp