| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
| --- This message came from the IEEE 802.11 Working Group Reflector ---
Hi Rob, Yes, this works with all the curves listed. But NIST p521, Brainpool p384, and Brainpool p512 all have primes such that p = 3 mod 4 (it was one of the design considerations by the Brainpool, see section 2.2 of RFC 5639). The only weirdo is NIST p224 (which has, as you note, p = 1 mod 4) but it still works with SSWU. I have implemented this and it works fine with all the curves. There is no restriction on this Simplified SWU to only work with curves where p = 3 mod 4. It will work with any Weierstrass curve where a != 0 and b != 0 per section 6.5.2 of the draft. But it does not map to the entire curve so just doing PT(m) = SSWU(h1(m)) is not sufficient. If you look closely at the Brier paper you'll notice that PT(m) = f(h1(m)) + f(h2(m)) is actually a construct they propose for Icart but said it didn't work with SWU, hence the PT(m) = f(h1(m)) + h2(m) * G. But the Simplified SWU from the draft can be used with Brier et al's Icart construction (I did check this with the cryptographer writing the draft) so that's what is being proposed. Check out section 3 of the draft and you'll note that what you propose—PT = SSWU(h1(m))—is the "Non-uniform encoding" which the authors note, "The distribution of the output is not uniformly random in G." Not being uniformly random is a problem because otherwise it would give an advantage to an attacker. So the authors define the "Random oracle encoding" which is what is being proposed in 11-19/1173—PT(m) = SSWU(h1(m)) + SSWU(h2(m)). The authors say of this encoding "The distribution of the output is indistinguishable from uniformly random in G provided that map_to_curve is 'well distributed' ([FFSTV13], Def. 1).
All of the map_to_curve functions defined in Section 6 meet this requirement." The Simplified SWU algorithm is defined in section 6 of that draft so it is therefore "well distributed" and therefore the "Random Oracle encoding" is the right way to go. That way the output will be indistinguishable from uniformly random.
I hope I have assuaged your concerns. If not please raise them again. regards, Dan. On 8/8/19, 8:42 AM, "Rob Sun" <Rob.Sun@xxxxxxxxxx> wrote: Hi Dan: Thanks for your clarification. I think I got your new scheme. You are using SSWU twice to generate a point instead of the Brier’s construction. However for indistinguishability, I think (1)
equals to the single use SSWU, specifically PT(M):= SSWU (h1(m)) is sufficient to map a password to the curve point. My concern is now with the use of the SSWU, the simplistic SSWU works for any curve over F(p^n), where P
≡3 mod 4 [draft-irtf-cfrg-hash-to-curve]. In your submission, I found the following curves in table 12 not suitable
for this scheme. NIST P 521 : P = 2^521 – 1
≡2 mod 4 NIST P 224 : P = 2^224 – 2^96 + 1
≡1 mod 4 Brainpool P384: P = 8CB91E82A3386D280F5D6F7E50E641DF152F7109ED5456B412B1DA197FB71123ACD3A729901D1A71874700133107EC53
≡1 mod 4 Brainpool P512: P= AADD9DB8DBE9C48B3FD4E6AE33C9FC07CB308DB3B3C9D20ED6639CCA703308717D4D9B009BC66842AECDA12AE6A380E62881FF2F2D82C68528AA6056583A 48F3
≡0 mod 4
You may want to double check if these curves can work with the SSWU. Thanks Rob From: Harkins, Daniel [mailto:daniel.harkins@xxxxxxx]
Hi Rob, On 8/2/19, 12:48 PM, "Rob Sun" <Rob.Sun@xxxxxxxxxx> wrote: Hi Dan: Thanks for your updated “SAE with SSWU” proposal, I have a few questions and comments : Q1: I have noticed you updated the PT generation from previous version with:
PT(m) := SSWU(h1(m)) + SSWU(h2(m)) (1),
rather PT(m) := SWU(h1(m)) + h2(m) * G (2) , Which was in your previous version of submission. I would assume equation (1) can be expanded as: PT(m) := SSWU(h1(m)) + SSWU(h2(m)) = SWU(h1(m))+ h1(m)*G + SWU(h2(m))+h2(m)*G, with SSWU denotes Brier’s simplified SWU construction, where both the addition are the points addition on the
curve. There are two observations: No, there's no expansion. It is just equation (1). You call SSWU() twice with different "u" values and sum their output. (2) was necessary because the SWU method required some finesse to be provable in the ROM without it but the Simplified SWU now being proposed does not have that problem. SSWU() is not the same as SWU().
[RS] Got it. You are using SSWU twice to generate a point instead of the Brier’s construction. However for indistinguishability, I think (1) equals to the single
use, specifically PT(M):= SSWU (h1(m)) is sufficiently to map a password to the curve point.
i)
Equation (1) involves 3 points additions vs 1 point addition in Equation (2), hence overhead is my concern.
ii)
From indistinguishability point of view, equation (1) is essentially equivalent to (2) in terms of the Random Oracle Encodings.
My question is any particular reasons to update the PT generation from (2) to (1)? From my perspective, equation (1) doesn’t provide any enhancement from (1) in indistinguishability.
Q2: Related to Q1, I think equation (1) is another type of simple hash to curve construction in Brier’s paper, but he admits that using construction (similar to equation (1)) convert to SWU wouldn’t be that
simple (equation (1) is more suitable for Icart’s function ( Page 3 of Brier’s paper).
It's not SWU, it's the "Simplified SWU" and that can be used as (1). SWU cannot and that's why the previous version of the submission had the (2) construct, because it was plain-jane SWU. This is not plain-jane SWU, it is the "Simplified SWU".
Q3: I am yet on the same page of PWE generation needs to be ROM (Random Oracle Model) proof. My understanding is the PWE generation is merely a function of mapping a arbitrary bit string to a curve point,
then the SAE (Dragonfly) protocol part provides the ROM proof. SSWU generation is proved to be ROM encoding in Brier’s paper. In another words, should there be simpler solution than the SWU? i.e the naïve encoding by H(m)*G which is also running in constant
time and efficient. Well yes, there is a simpler solution than SWU. It's the "Simplified SWU" that I am proposing in r9! Feel free to generate your own proof of the protocol that does not require PWE generation in the ROM. In the meantime, I think it is most prudent to go with what's in the submission. regards, Dan. From: Harkins, Daniel [mailto:daniel.harkins@xxxxxxx]
--- This message came from the IEEE 802.11 Working Group Reflector ---
Hello, I have updated 11-19/1173 to do the "Simplified SWU" method of hashing to a curve. This supports all the curves possible with SAE and is more efficient that the previous version. It can be implemented in constant time which will mitigate the side channel and timing attacks described in the recent "Dragonblood" paper. In addition, it mitigates a group downgrade attack (also described in that paper).
https://mentor.ieee.org/802.11/dcn/19/11-19-1173-09-000m-pwe-in-constant-time.docx Please take a look. I have implemented this so I know it works. The question is, though, is this specified in a clear enough way for others to implement.
regards,
Dan. To unsubscribe from the STDS-802-11 list, click the following link:
https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11&A=1 To unsubscribe from the STDS-802-11 list, click the following link: https://listserv.ieee.org/cgi-bin/wa?SUBED1=STDS-802-11&A=1 |