<div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small">On Sun, Jan 6, 2019 at 9:56 AM Mark Steward <<a href="mailto:marksteward@gmail.com">marksteward@gmail.com</a>> wrote:<br></div></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On Sat, Jan 5, 2019 at 10:26 PM Phillip Hallam-Baker<br>
<<a href="mailto:phill@hallambaker.com" target="_blank">phill@hallambaker.com</a>> wrote:<br>
><br>
I don't mean "why use an HMAC", I mean why take 512 bits of random,<br>
truncate them to 117 bits (by prefixing 8 constant bits and calling<br>
P), and then stretch the output and pretend it's 512 bits? Why then<br>
prefix content type unless you're anticipating reusing keys? And why<br>
truncate the final output to 117 bits again, and format it like it's<br>
something to be entered by hand, when a simple HMAC would suffice?<br>
There must be a reason you've chosen this inscrutable structure.<br></blockquote><div><br></div><div><div class="gmail_default" style="font-size:small">[Thanks for the feedback here it is helping, the design has evolved over time and not all the features may be apparent.]</div><br></div><div><br></div><div><div class="gmail_default" style="font-size:small">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.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">This is the latest draft but it is not complete. It may still have the previous construction in places that did not use HMAC.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default"><a href="https://tools.ietf.org/html/draft-hallambaker-udf-12">https://tools.ietf.org/html/draft-hallambaker-udf-12</a><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">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:</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><pre class="gmail-newpage" style="font-size:13.3333px;margin-top:0px;margin-bottom:0px;break-before:page;color:rgb(0,0,0)">MDDK7-N6A72-7AJZN-OSTRX-XKS7D</pre></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">That is something I can put on my business card. But it is still a little long. Hence the need for the compressed version:</div><br></div><div><div class="gmail_default" style="font-size:small"><span style="color:rgb(0,0,0);font-size:13.3333px">ME522-SXCSN-BFY3H-JBAAD</span></div><br></div><div><div class="gmail_default" style="font-size:small">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.</div><br></div><div><div class="gmail_default" style="font-size:small">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.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">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.</div></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I can't make sense of what you're trying to say here. The initial<br>
zeroes are part of the hash, not leading zeroes from prime numbers or<br>
similar. If you removed this suspicious and buggy functionality, would<br>
that break anything?<br></blockquote><div><br></div><div><div class="gmail_default" style="font-size:small">It would not break anything at the technical level but it would make the usability worse. </div><br></div><div><div class="gmail_default" style="font-size:small">One of the antipatterns I see when using BASE32 fingerprints is that folk end up generating fingerprints like MONEY-<span style="color:rgb(0,0,0);font-size:13.3333px">SXCSN-BFY3H-JBAAD</span><span style="color:rgb(0,0,0);font-size:13.3333px">-XKS7D</span> or</div><div class="gmail_default" style="font-size:small"><span style="color:rgb(0,0,0);font-size:13.3333px">MICRO-SOFTN-BFY3H-JBAAD</span><span style="color:rgb(0,0,0);font-size:13.3333px">-XKS7D</span></div><br></div><div><div class="gmail_default" style="font-size:small">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</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">MONEY-<span style="color:rgb(0,0,0);font-size:13.3333px">SX</span><span style="color:rgb(0,0,0);font-size:13.3333px">GDR-KG47R-7OVPT</span><span style="color:rgb(0,0,0);font-size:13.3333px">-OSTRX</span></div><div class="gmail_default" style="font-size:small"><span style="color:rgb(0,0,0);font-size:13.3333px"><br></span></div><div class="gmail_default" style="font-size:small">That is completely different but is going to be confused. For even more confusion, match the first and last segments:</div><br></div><div><div class="gmail_default" style="font-size:small">MONEY-<span style="color:rgb(0,0,0);font-size:13.3333px">SXCSN-BFY3H-JBAAD</span><span style="color:rgb(0,0,0);font-size:13.3333px">-XKS7D</span></div></div><div><div class="gmail_default" style="font-size:small">MONEY-<span style="color:rgb(0,0,0);font-size:13.3333px">SX</span><span style="color:rgb(0,0,0);font-size:13.3333px">GDR-KG47R-7OVPT</span><span style="color:rgb(0,0,0);font-size:13.3333px">-XKS7D</span></div></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
>> Your convenient Validate function isn't constant time:<br>
>><br>
>>   <a href="https://github.com/hallambaker/Mathematical-Mesh/blob/8f309a1/Libraries/Goedel.Cryptography/UDF.cs#L407-L408" rel="noreferrer" target="_blank">https://github.com/hallambaker/Mathematical-Mesh/blob/8f309a1/Libraries/Goedel.Cryptography/UDF.cs#L407-L408</a><br>
><br>
><br>
> Probably not. That is currently just a placeholder. It doesn't even accept longer fingerprints to check against shorter patterns.<br>
><br>
<br>
Checking shortened fingerprints is an antipattern, as demonstrated by<br>
GPG short key collisions. If humans need to enter hashes by hand,<br>
something's gone very wrong already.<br></blockquote><div><br></div><div><div class="gmail_default" style="font-size:small">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.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">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.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">1) User sets up new device, it reports its UDF as <span style="color:rgb(0,0,0);font-size:13.3333px">MDDK7-N6A72-7AJZN-OSTRX-XKS7D</span></div><br></div><div class="gmail_default" style="font-size:small">2) 

User cuts and pastes the UDF into an admin tool</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">3) Admin tool talks to device, gets the document corresponding to the UDF, calculates the long UDF: <span style="color:rgb(0,0,0);font-size:13.3333px">MDDK7-N6A72-7AJZN-OSTRX-XKS7D-JAFXI-6OZSL-U2VOA-</span><span style="color:rgb(0,0,0);font-size:13.3333px">TZQ6J-MHPTS</span></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">4) Admin tool determines that the user fingerprint matches the one calculated and declares it a match</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">5) Admin tool stores the 250 bit fingerprint in the device database.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
> 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.<br>
><br>
<br>
Are you talking about the patent from 1998? I don't see how that can<br>
help with hash comparison.<br></blockquote><div><br></div><div class="gmail_default" style="font-size:small">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.</div></div></div></div>