[Cryptography] Is there any advantage to canonical fingerprints.

Phillip Hallam-Baker phill at hallambaker.com
Mon Oct 2 14:05:51 EDT 2017

So I was working on my UDF fingerprint scheme. Using base32 to encode a
fingerprint and adding an 8 byte version prefix means that a fingerprint
with a 117 bit work factor looks like this:


Its not bad but how about we ease up on the work factor. The absolute
minimum I would want to have is 92 bits.

Now suppose that the first 25 bits of the fingerprint are zeros. The 92 bit
fingerprint that would look like this:


Now looks like this:


It is the exact same workfactor as all we have done is used compression.
The version byte indicator is 97 instead of 96 to show that 25 leading
zeros were omitted.

Finding that fingerprint ("290668103" in text/plain) by exhaustive search
took me about 10 minutes using a single core. To save another character, or
improve the work factor by 5 bits will take 32 times as long. Which is
manageable if I multithread the code for all 12 cores. But going much
beyond that is going to be impractical without a BIG machine.

If I am taking a fingerprint of an ECDH key, the keygen overhead is not
terrible. But I certainly can't compress RSA keys this way. And I really
can't see saving more than 25 bits of work factor being practical unless
either I use the GPU or rent space on a BitCoin mining farm or the like.

Point being that if I am going to do either, I am really going to want to
calculate H(Key+Salt) and do exhaustive search on the salt rather than
H(Key) and vary the Key.

To reduce the fingerprint to a memorable 10 characters would take a million
times the compute power I used to shorten to 15. But I can see some people
being willing to pay for that.

My brief investigation suggests that current bitcoin mining difficulty*
is 1123863285133, or 2^40. So assuming people are spending less than the
coins are worth to mint them, say $1000, getting to a 10 character
fingerprint would cost a million bucks right now. Which means only pharma
Bro is gonna be buying and that after he gets outta club Fed.

But going the other way, 35 bits of compression is $4 worth of compute
power. And that means 102 bit work factor in 15 characters. Which fits on a
business card.


One of the innovations in PrismProof email is Strong Internet names that
allow fingerprints to be used as DNS name components, thusy:

alice at example.com
mail to Alice without requiring security enhancements.
alice at mm--mf2gk-6duf5-ygyyl.example.com
mail to Alice. If the MUA is SIN-Aware, it MUST resolve the security policy
specified by the fingerprint and apply security enhancements as mandated by
that policy.
alice at example.com.mm--mf2gk-6duf5-ygyyl
send mail to Alice if the MUA is SIN-Aware, it MUST resolve the security
policy specified by the fingerprint and apply security enhancements as
mandated by that policy.

More info in:


[*]Yes, I know BitCoin uses SHA256. I deliberately chose SHA512 for that
exact reason as the ASIC is only going to do SHA512 if it is designed for
that purpose.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20171002/f73b952c/attachment.html>

More information about the cryptography mailing list