2
$\begingroup$

So I'm trying to compare different digital signatures, and thus I stumbled upon a DSA algorithm. I'm using python's cryptography library, and it offers following values for L and N:

  • L=1024,N=160
  • L=2048,N=256
  • L=3072,N=256
  • L=4096,N=256

I'm wondering what are security levels of those pairs. I found this table from NIST publication, but it doesn't really cover them.

enter image description here

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Does this answer your question? Why do we use 1024 / 160 bit primes in DSA? $\endgroup$
    – kelalaka
    Jun 15, 2022 at 20:44
  • $\begingroup$ Soo, basically N kinda determines the security level? $\endgroup$
    – ksi3m
    Jun 15, 2022 at 21:28
  • $\begingroup$ No. $N$ determines the difficulty of one of two attacks on the discrete logarithm problem; $L$ determines the difficulty of another. The overall security is the minimum of the two. See my answer below. $\endgroup$
    – Daniel S
    Jun 16, 2022 at 6:53

2 Answers 2

Reset to default
4
$\begingroup$

As noted in the answer to Why do we use 1024 / 160 bit primes in DSA?, the security of DSA needs to worry about two attacks (neither of which should be described as factorisation).

There is the general number field sieve (GNFS) index calculus attack that depends on $L$. Calculating the difficulty of an GNFS attack accurately is not easy to describe, but can be looked up in tables such as the one that you quote above. The only missing value is $L=4096$ which (according to the RFC 3766 method on keylength.com is about 142-bits of security.

The other attack is to use a method similar to Pollard's kangaroo which will require roughly $2^{N/2}$ multiplications of $L$-bit numbers. Most people will then describe this as $N/2$-bits of security per your table.

The overall security is at best the minimum of these two values. We now see that the python option offer mismatched levels of security in some cases, which is not illegal but may be inefficient. The overall security offered for each pair is then

Parameters GNFS security Pollard security Overall security
1024/160 80 80 80
2048/256 112 128 112
3072/256 128 128 128
4096/256 142 128 128
Improve this answer
$\endgroup$
-1
$\begingroup$

DSA is asymmetric,the key size should be > 1024, possible attack factorisation, Large key sizes and hash values discourage attacks of this type but there are always smarter approaches.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is duplicate, and this answer is not better than or distinct than the duplicate. $\endgroup$
    – kelalaka
    Jun 15, 2022 at 21:22
  • 1
    $\begingroup$ Factorization is essentially of no help against DSA. It makes sense to compare the security of an asymmetric algorithm to that of a symmetric key algorithm, that's what the question asks, and 1024 (bit) is not in the right ballpark for that. "There are always smarter approaches" is plausible, but not useful, as it's entirely compatible with the plausible possibility there's no approach that can solve a given problem with a feasible effort and sizable probability. This leaves "Large key sizes and hash values discourage attacks of this type" as the only actionable truth in this answer. $\endgroup$
    – fgrieu-onstrike ♦
    Jun 16, 2022 at 6:59
  • $\begingroup$ @fgrieu are you aware of number field sieve algorithm and how it works ? $\endgroup$
    – Pegasus
    Dec 12, 2022 at 23:14
  • $\begingroup$ @Pegasus: yes I'm aware of NFS, and it's variant actionable against DSA (especially at the 1024/160 level), but not well-enough to explain it. I can suggest this as a source of relatively state-of-the art bibliography. $\endgroup$
    – fgrieu-onstrike ♦
    Dec 13, 2022 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.