[Cryptography] Blockchain without proof of work

Phillip Hallam-Baker phill at hallambaker.com
Sat Jan 5 17:25:49 EST 2019


On Sat, Jan 5, 2019 at 2:55 PM Mark Steward <marksteward at gmail.com> wrote:

> On Sat, Jan 5, 2019 at 7:46 AM Phillip Hallam-Baker
> <phill at hallambaker.com> wrote:
> ...
> >> > UDF=KD25H-GSNE2-JVVJE-RXTMA-7VAWT
> >> > UDF=KCOO3-EKPAG-FKYFC-O2B2N-O3UUA
> >> > UDF=KBR3A-RQLV7-SMB6X-6OB7X-JMBNT
> ...
> >
> > OK so I have decided to make a few changes to the structure here so the
> values will change.
> >
> > Let us say that m = "Konrad is a Kompromised agent".
> > first choose a random key kt = P (0xB0 || rand (512), 125)
> > (where P is the presentation/truncation function using Base32 putting in
> dashes every 5 characters and truncating to 125 bits)
> >
> > We use SHA-2-512 to construct a Keyed UDF, so HKDF(), H(), HMAC() are
> functions all using that as the base digest:
> >
> > k = HKDF (kt, 512)
> > f = HMAC (k, ct || ':' || H(m))
> > udf = P((v || f), 125)
> >
> > Where v is simply a tag to identify the fingerprint type and ct is the
> IANA content type
> >
>
> So that's effectively just HMAC(rand(117), m), truncated to 120 bits
> (i.e. a birthday complexity of 60 bits). What purpose does the
> obfuscation serve?
>

A straight hash function would allow a dictionary attack. Adding in the key
means that a brute force attack has a work factor of the dictionary size
times 2^512 which is obviously infeasible.


> > So the core here is that we have a fingerprint of the data that can only
> be verified if the key kt is known. Since this is a keyed digest, we are
> using an HMAC for the purpose.
> >
> > I have pushed out the code to GitHub but I need to clean it up a bit.
>
> Is that this code?
>
>
> https://github.com/hallambaker/Mathematical-Mesh/blob/8f309a1/Libraries/Goedel.Cryptography/UDF.cs#L212-L222
>
> That link is to some bizarre functionality to "compress" the output by
> adding the number of leading zero bytes to the versionID, which
> further reduces the hash to 117 bits, and allows fingerprints from two
> different versions to collide.
>

That is important and useful functionality for key fingerprints. The
compression function does not affect the brute force work factor for the
attacker. What it means is that if the user puts in a Work Factor of 2^24
on key generation, the work factor of the resulting 125 bit fingerprint
will be 2^(117+24) rather than 2^117.

That is a standard construction that has been reviewed by the IETF.
Unfortunately, there is a patent on a particular approach held by
Microsoft. While they have licensed that for certain IETF protocols, it is
not generally licensed.


> 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.



> And throughout this library you've wrapped all the crypto functions in
> a way that obscure their nature and leads to typos:
>
>
> https://github.com/hallambaker/Mathematical-Mesh/blob/8f309a1/Libraries/Goedel.Cryptography/UDF.cs#L39
>
> https://github.com/hallambaker/Mathematical-Mesh/blob/8f309a1/Libraries/Goedel.Cryptography/Standard/Digest.cs#L440
>
> https://github.com/hallambaker/Mathematical-Mesh/blob/8f309a1/Libraries/Goedel.Cryptography/Standard/Digest.cs#L515
>
> https://github.com/hallambaker/Mathematical-Mesh/blob/8f309a1/Libraries/Goedel.Cryptography/Algorithms/SHA3Managed.cs#L94
>

That is historical due to the fact that .NET was changing as I was writing
the code. So when I originally wrote the code it had to be able to swap out
the core crypto depending on whether it was Mono or .NET Framework.
Microsoft has since fixed that and I am currently going through the code to
eliminate the historical functions.

I would really like it if Microsoft would get with the program and actually
implement SHA3, Ed448, Ed22519, X448 and X25519. And I expect they will.
but in the meantime, I had to write some placeholder code.

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190105/c26b7985/attachment.html>


More information about the cryptography mailing list