Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

["Blumenthal, Uri - 0668 - MITLL" <[e-mail]>]

> I believe your main concern is the double use of the signer¹s secret ³x²
> value.   As you point out, we are
> ³betting the farm² that ALL of the ³k²¹s produced by the HMAC_DRBG are strong.
> I¹ve not seen any reason
> to doubt the strength of HMAC_DRBG.
Would this reference http://www.springerlink.com/content/j7340u8162582044/
shake your confidence? (David K., thanks for pointing me at it.) Its
abstract says (again, thanks, David):

> Applications of an iterated hash function such as HMAC require that the
> compression function of the hash function is a pseudorandom function. However,
> the pseudorandom-function property of the compression function was not
> analyzed up to now. This paper shows that it is easy to distinguish between
> the 22 step-reduced SHA-512 compression function with the key-via-IV strategy
> and a random function. This is the first result on the pseudorandom-function
> property of the SHA-512 compression function with the key-via-IV strategy. A
> similar distinguishing attack is applicable to the SHA-256 compression
> function with the key-via-IV strategy.

For their distinguisher they computed prf-advantage as 2^-12 with 4 queries.
Advantage increases with the number of queries, as should be expected.

HMAC is pseudorandom only if the underlying compression function is
pseudorandom. SHA2 may not be pseudorandom.

> But I also would strongly encourage you and your co-authors
> to put forth a more daring and an efficient alternative design, one that will
> require more extensive analysis
> before it is ready for adoption.

A good alternative IMHO would be using a block cipher-based compression
function.

Tnx!



> From: David W. Kravitz [mailto:[e-mail]]
> Sent: Monday, September 24, 2012 11:30 AM
> To: Igoe, Kevin M.; [e-mail]
> Cc: [e-mail]; [e-mail]; [e-mail]
> Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
> Digital Signature Algorithms
>  
> Kevin,
>  
> One effect of the use of ³internal state² is the prevention of HMAC_DRBG from
> producing repeat outputs, where ³HMAC_DRBG Internal State² is defined in
> section 10.1.2.1 of SP 800-90A. By stating that ³Note that we instantiate a
> new HMAC_DRBG instance for each signature generation process,² the draft is
> indicating that internal state is not carried over (which is what I meant by
> ³null²). Consequently, given a repeat message Œm¹ (i.e., repeat seed (= x ||
> H(m) )), the output repeats. While this is not a problem in this particular
> application, it violates a fundamental property of a good DRBG. Furthermore,
> with regard to the next-output-bits-given-previous-output-bits- uncertainty
> property of a good DRBG, if the output for a single message Œm¹ becomes known,
> all other outputs are not only distinguishable from the output of a truly
> random function, but are actually computable. This is due to the ³double use²
> of the private key Œx¹ for generation of Œk¹ and for generation of Œs¹ from
> Œk¹. Since we don¹t require the use of a DRBG in this (EC)DSA application, we
> can use HMAC directly (with Œx¹ as the HMAC key, and H(m)||Counter as the
> HMAC¹ed data, where Counter is used in conjunction with FIPS PUB 186-3 B.2.1
> or B.2.2).
>  
> Note that the use of deterministic generation of Œk¹ (whether done as in the
> current draft, or the suggested simplified version, or based on a block cipher
> instead of HMAC) has an additional potential non-repudiation advantage not
> previously explicitly mentioned: It could make it more difficult to plausibly
> disavow signatures on the basis of leakage of Œx¹ due to low entropy Œk¹.
>  
> Thanks,
> David
>  
> 
> From: Igoe, Kevin M. [mailto:[e-mail]]
> Sent: Monday, September 24, 2012 10:21 AM
> To: 'David W. Kravitz'; [e-mail]
> Cc: [e-mail]; [e-mail]
> Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
> Digital Signature Algorithms
>  
> David:
>  
>   I¹m having a hard time parsing the last two sentences of the first
> paragraph.  Would you be kind
> enough to rephrase them for me?
>  
> 1) As far as I can see this draft instantiates the HMAC_DRBG using the seed (=
> x || H(M) ) in 
> precisely the correct manner.  I miss where they have strayed from the
> standard.  
>  
> 2) I¹m not  sure what you mean by ³null internal state².
>  
> Clearly I am misinterpreting what you are trying to say.
>  
> 
> From:[e-mail] [mailto:[e-mail]] On Behalf Of David
> W. Kravitz
> Sent: Wednesday, September 19, 2012 6:40 PM
> To: [e-mail]
> Cc: [e-mail]; [e-mail]
> Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
> Digital Signature Algorithms
>  
> Hi all,
>  
> Comments below.
>  
> Thanks,
> Jon Callas, David W. Kravitz, and Phil Zimmermann
>  
> The required security attributes for the safe use of HMAC in this draft are
> more nuanced than the description currently conveys.  Consider the following
> two excerpts of the draft from the Security Considerations (section 5):
> ³Security relies on whether the generation of 'k' is indistinguishable from
> the output of a Random Oracle.  Roughly speaking, HMAC_DRBG is secure in that
> role as long as HMAC behaves as a PRF (Pseudo-Random Function).²   ³One
> remaining issue with deterministic (EC)DSA, as presented in this document, is
> the "double use" of the private key 'x', both as private key in the signature
> generation algorithm itself, and as input to the HMAC_DRBG-based pseudo-random
> oracle for producing the 'k' value.  This requires HMAC_DRBG to keep on being
> a random oracle, even when the public key (which is computed from 'x') is also
> known.  Given the lack of common structure between HMAC and discrete
> logarithm, this seems a reasonable assumption.² Any discussion in the
> literature of ³random oracle² is typically with respect to ³a publicly
> accessible random function² (as, for example, in ³Indifferentiability,
> Impossibility Results on Reductions, and Applications to the Random Oracle
> Methodology,² by U. Maurer, R. Renner, and C. Holenstein,
> ftp://ftp.inf.ethz.ch/pub/crypto/publications/MaReHo04.pdf). But as HMAC_DRBG
> is specified in the draft document (with null internal state per ³Note that we
> instantiate a new HMAC_DRBG instance for each signature generation process,²
> and ³double use² of the private key Œx¹), given any single output of
> HMAC_DRBG, all other outputs are completely distinguishable from the output of
> an arbitrary truly random function. In other words, given a single Œk¹ value
> that was generated using HMAC_DRBG as specified, any other Œk¹ value(s)
> recovered from Œs¹ by using Œr¹, ŒH(m)¹ and the no-longer-private value of Œx¹
> can be determined as having been generated using HMAC_DRBG as specified. Note
> that even if no values of Œk¹ are disclosed, the use of null internal state
> would be problematic in an application relying on a DRBG where repeated
> outputs are unacceptable.
>  
> So, given that neither (pseudo-)random oracle nor the
> next-output-bits-given-previous-output-bits- uncertainty property of DRBG is
> achieved within the context of the actual (EC)DSA application, we can use a
> simpler formulation here. An example of such is HMAC(Œx¹, H(m)||Counter),
> where Counter is reinitialized for each signature generation process instance
> and potential bias is addressed by deriving Œk¹ using  a single Counter value
> as in [FIPS PUB 186-3] B.2.2 (Per-Message Secret Number Generation by Testing
> Candidates), or multiple Counter values are used as in B.2.1 (Per-Message
> Secret Number Generation Using Extra Random Bits).
>  
> Note that in the case where multiple entities have knowledge of Œx¹ (which may
> complicate non-repudiation), deterministic generation of Œk¹ has the effect
> that the potential subliminal/covert channel is replaced by a MAC property.
> That is, any entity with knowledge of Œx¹ can verify the integrity of Œm¹
> using Œs¹ while ignoring both the transmitted value of Œr¹, and Œy¹ or ŒU¹
> (where y = g^x mod p in DSA or U = xG in ECDSA).
>  
> It might also be prudent to indicate in the Security Considerations section
> that the use of wholly deterministic generation of Œk¹, while not adversely
> affecting the security of (EC)DSA itself and enabling an implementation to be
> safely tested using dummy values of Œx¹, may have a deleterious effect against
> resistance to side-channel attacks such as DPA (as opposed to ³masking² using
> a true RNG).
>  
>  
> 
> From: "David McGrew (mcgrew)" <[e-mail]>
> 
> Subject: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital
> Signature Algorithms
> 
> Date: September 13, 2012 7:40:41 AM PDT
> 
> To: "[e-mail]" <[e-mail]>
>  
> 
> Hi,
> 
>  
> 
> Thomas has updated his individual submission on deterministic [EC]DSA.   I
> think this is useful work that deserves to move forward to RFC, and that the
> research group should support it (based on my own opinion and the positive
> feedback on the list regarding version ­00).   Please take a look at the draft
> if you have an opinion on digital signatures, and let Thomas know if you have
> constructive criticism.   Verification of the test cases, and review of the
> security considerations, would be especially helpful.
> 
>  
> 
> Thanks,
> 
>  
> 
> David
> 
>  
> 
> <http://tools.ietf.org/html/draft-pornin-deterministic-dsa-01>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>