[Cryptography] Blockchain without proof of work

[Phillip Hallam-Baker]

On Sun, Jan 6, 2019 at 9:56 AM Mark Steward <marksteward at gmail.com> wrote:

> On Sat, Jan 5, 2019 at 10:26 PM Phillip Hallam-Baker
> <phill at hallambaker.com> wrote:
> >
> I don't mean "why use an HMAC", I mean why take 512 bits of random,
> truncate them to 117 bits (by prefixing 8 constant bits and calling
> P), and then stretch the output and pretend it's 512 bits? Why then
> prefix content type unless you're anticipating reusing keys? And why
> truncate the final output to 117 bits again, and format it like it's
> something to be entered by hand, when a simple HMAC would suffice?
> There must be a reason you've chosen this inscrutable structure.
>

[Thanks for the feedback here it is helping, the design has evolved over
time and not all the features may be apparent.]


I think your confusion is probably due to the fact that I haven't pushed
out the draft yet which gives the context. This is a fingerprint scheme
that has been extended to support commitments. It was not designed as a
pure commitment scheme.

This is the latest draft but it is not complete. It may still have the
previous construction in places that did not use HMAC.

https://tools.ietf.org/html/draft-hallambaker-udf-12

The starting point is I wanted a more robust, flexible PGP fingerprint
scheme that protects against semantic substitution, has a readable
presentation, etc. So a UDF fingerprint with a work factor approximating to
the 128 bits we like to work from (actually 117 bits) looks like this:

MDDK7-N6A72-7AJZN-OSTRX-XKS7D


That is something I can put on my business card. But it is still a little
long. Hence the need for the compressed version:

ME522-SXCSN-BFY3H-JBAAD

That has a work factor of 116 bits. If I could press my GPUs into service,
I could generate a public key with a 124 bit work factor without too much
inconvenience.

The reason for rendering the key as text is that it allows me to write it
down on paper without going to a printer. We only need as many bits of
randomness in the input to the HMAC as we will report in the output.

It is stretched to 512 bits using HKDF because that is the function that is
designed to convert strings to keys. It is overkill for this purpose but it
means I use the same function everywhere.

I can't make sense of what you're trying to say here. The initial
> zeroes are part of the hash, not leading zeroes from prime numbers or
> similar. If you removed this suspicious and buggy functionality, would
> that break anything?
>

It would not break anything at the technical level but it would make the
usability worse.

One of the antipatterns I see when using BASE32 fingerprints is that folk
end up generating fingerprints like MONEY-SXCSN-BFY3H-JBAAD-XKS7D or
MICRO-SOFTN-BFY3H-JBAAD-XKS7D

Which seems great at first until you realize that a human is only ever
going to check the readable part. so now there is an in for the attacker
who generates

MONEY-SXGDR-KG47R-7OVPT-OSTRX

That is completely different but is going to be confused. For even more
confusion, match the first and last segments:

MONEY-SXCSN-BFY3H-JBAAD-XKS7D
MONEY-SXGDR-KG47R-7OVPT-XKS7D


> >> Your convenient Validate function isn't constant time:
> >>
> >>
> https://github.com/hallambaker/Mathematical-Mesh/blob/8f309a1/Libraries/Goedel.Cryptography/UDF.cs#L407-L408
> >
> >
> > Probably not. That is currently just a placeholder. It doesn't even
> accept longer fingerprints to check against shorter patterns.
> >
>
> Checking shortened fingerprints is an antipattern, as demonstrated by
> GPG short key collisions. If humans need to enter hashes by hand,
> something's gone very wrong already.
>

I disagree. Humans do need to be able to enter fingerprints in certain
circumstances. But the short fingerprints should never have a work factor
of less than 2^110.

The long fingerprints in UDF are 250 or 500 bits. That is clearly not
something that a sysop should ever type. The situation in which I would see
these being used would be something like the following.

1) User sets up new device, it reports its UDF as
MDDK7-N6A72-7AJZN-OSTRX-XKS7D

2)  User cuts and pastes the UDF into an admin tool

3) Admin tool talks to device, gets the document corresponding to the UDF,
calculates the long UDF: MDDK7-N6A72-7AJZN-OSTRX-XKS7D-JAFXI-6OZSL-U2VOA-
TZQ6J-MHPTS

4) Admin tool determines that the user fingerprint matches the one
calculated and declares it a match

5) Admin tool stores the 250 bit fingerprint in the device database.



> I don't plan to rely on constant time implementation to protect against
> side channel attack. It tends to be brittle in the face of aggressive
> compiler optimization. The Kocher patents should expire soon if they
> haven't already and they provide a more powerful approach that I need to
> implement for other reasons.
> >
>
> Are you talking about the patent from 1998? I don't see how that can
> help with hash comparison.
>

I don't see how constant time would be relevant for a digest operation. The
implementations of Ed/X 448/25519 are not constant time because they are
only placeholders for use until Microsoft releases some proper
implementations.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190106/bba4ffa8/attachment.html>