Bit security of UOV 1.0 (and MAYO)
456 views
Skip to first unread message
Markku-Juhani O. Saarinen
Jun 3, 2024, 5:36:29 AMJun 3
to pqc-forum
Hi All,
Background & Summary:
Section 4 of the UOV 1.0 submission document [1] contains a concrete security analysis to justify its parameter selection. Analysis in Section 4.1 arrives at the estimate of 2^142.7 bit operations for the collision attack, which the authors round up to 2^143 for Table 5. Recall that the NIST call [3, Section 4.B.3] sets the Category 1 requirement at 2^143 classical gates, so this is very close indeed.
This analysis may overlook a trivial shortcut with the effect that the security of UOV-Is in fact falls a couple of bits short of the Category 1 requirement. MAYO [2] parameter sets seem to have the same issue.
Collision forgery attack:
Recall that verification in these schemes works in a traditional "RSA-like" hash-and-sign trapdoor manner; public map P is applied to the signature and the result is checked against the message hash.
To verify signature "sig" for message M:
t := H( [salt], M ) // hash message M (with salt, ignored in this discussion).
y := P(sig, pk) // public map (defined by pk) applied to sig.
if y == t then: the signature is valid
else: invalid
If we look at UOV parameter sets we note that sometimes the hash / P output length |y| == |t| has been chosen to be exactly twice the security level. This is of course the absolute minimum due to the Birthday paradox. For UOV-Is (and MAYO-1, MAYO-2) have m=64 and q=2^4; the variables y and t are 256 bits.
The algebraic shortcut:
The public quadratic maps "P" in many Oil-and-Vinegar - type multivariate schemes have a trivial algebraic property that if we multiply each finite field element in signature vector "sig" by a scalar constant "c", the elements of the public map output vector "y" get multiplied by its square "c^2":
The shortcut is to scale m-element vectors in both the "hash list" { H(M*) } and "public map list" { P(sig*, pk) } so that the lead element is 1 (if nonzero) in both. This is a simple scaling operation and reduces the 2-function image where a collision must occur by a factor of 1/(q-1).
Upon collision in these slightly reduced lists, we can adjust (scale) the signature preimage "sig" by a scalar c = sqrt( actual lead digit of H(M) ) so that it will match the actual hash H(M) = P(c*sig, pk). The pair (M, c*sig) is the forgery.
Since the "q" field is 4 bits, the speedup of this trick is its square root, or "2 bits". But as the analysis is already at the borderline, this might arguably push it below it.
References:
[1] "UOV 1.0" https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/UOV-spec-web.pdf
[2] "MAYO" https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/mayo-spec-web.pdf
[3] "Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process" https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/call-for-proposals-dig-sig-sept-2022.pdf
Best Regards,
-Markku
Section 4 of the UOV 1.0 submission document [1] contains a concrete security analysis to justify its parameter selection. Analysis in Section 4.1 arrives at the estimate of 2^142.7 bit operations for the collision attack, which the authors round up to 2^143 for Table 5. Recall that the NIST call [3, Section 4.B.3] sets the Category 1 requirement at 2^143 classical gates, so this is very close indeed.
This analysis may overlook a trivial shortcut with the effect that the security of UOV-Is in fact falls a couple of bits short of the Category 1 requirement. MAYO [2] parameter sets seem to have the same issue.
Collision forgery attack:
Recall that verification in these schemes works in a traditional "RSA-like" hash-and-sign trapdoor manner; public map P is applied to the signature and the result is checked against the message hash.
To verify signature "sig" for message M:
t := H( [salt], M ) // hash message M (with salt, ignored in this discussion).
y := P(sig, pk) // public map (defined by pk) applied to sig.
if y == t then: the signature is valid
else: invalid
In a collision forgery approach, we create a large list of hashes (and preimages m) { H(M*) }, and also apply the public map to a large number of random signature vectors to produce list { P(sig*, pk) }. A match H(m) = P(sig, pk) in the lists is a signature forgery, clearly violating EUF-CMA.
If we look at UOV parameter sets we note that sometimes the hash / P output length |y| == |t| has been chosen to be exactly twice the security level. This is of course the absolute minimum due to the Birthday paradox. For UOV-Is (and MAYO-1, MAYO-2) have m=64 and q=2^4; the variables y and t are 256 bits.
The algebraic shortcut:
The public quadratic maps "P" in many Oil-and-Vinegar - type multivariate schemes have a trivial algebraic property that if we multiply each finite field element in signature vector "sig" by a scalar constant "c", the elements of the public map output vector "y" get multiplied by its square "c^2":
P(sig, pk) = y <=> P(c*sig, pk) = c^2*y for any c != 0 in GF(q) [Eq. 1]
(Yes, even the linear "diagonal" coefficients are squared in public map evaluation, so everything ends up squared.)
Upon collision in these slightly reduced lists, we can adjust (scale) the signature preimage "sig" by a scalar c = sqrt( actual lead digit of H(M) ) so that it will match the actual hash H(M) = P(c*sig, pk). The pair (M, c*sig) is the forgery.
Since the "q" field is 4 bits, the speedup of this trick is its square root, or "2 bits". But as the analysis is already at the borderline, this might arguably push it below it.
The practical impact of this attack is of course marginal with these parameter selections.
[1] "UOV 1.0" https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/UOV-spec-web.pdf
[2] "MAYO" https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/round-1/spec-files/mayo-spec-web.pdf
[3] "Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process" https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/call-for-proposals-dig-sig-sept-2022.pdf
-Markku
Ward Beullens
Jun 3, 2024, 8:23:11 AMJun 3
to pqc-forum, Markku-Juhani O. Saarinen
Hi Markku,Thanks a lot for looking into this and pointing out this nice trick that was overlooked in the UOV and MAYO specs, which should indeed reduce the cost of a collision search by a factor sqrt(q) = 4. We will include this in future versions of the MAYO spec.I can't help but point out that the 2^142.7 number you quote is not an estimate, but rather a lower bound accounting only for the cost of computing the lists, and ignoring the cost of actually finding the collision between the lists. (which could e.g. be done by sorting and matching, or by doing something like Pollard rho or van Oorschot-Wiener, each of which comes with some overhead).Regards,
Ward (on behalf of the MAYO team)
Ward (on behalf of the MAYO team)
Op maandag 3 juni 2024 om 11:36:29 UTC+2 schreef Markku-Juhani O. Saarinen:
Reply all
Reply to author
Forward
0 new messages