Cisco ASA Devices on the Naughty Step, Again?

The patch hasn’t worked?

And, so, at the core of your security is the generation of random numbers. Why? Well, we need true randomness to generate encryption keys and also for digital signing with ECDSA.

In ECDSA, we use a random nonce as part of the signature process, and if this is not random, it may be possible to reveal the private key of the signer. In Figure 1, we see that a value of k is used to create s, and where (r,s) is the signature of a message that is signed with Bob’s private key.

At, Real World Crypto 2023, a new presentation has shown that on a Cisco ASA device, 26% of ECDSA signatures from the device had duplicate ECDSA nonces, and 36% of them had duplicate ECDSA keys. Along with this they found that 6% of self-signed RSA certificates had the same RSA moduli. For the RSA moduli matches, it means that the same prime numbers (p and q) were used in the creation of the key:

Ref: [here]

The vulnerability seems to relate to CVE-2023–20107, and where the Cisco ASA (Adaptive Security Appliance) device produces low-entropy keys [here]:

CVE-2023–20107 [here]

Cisco Vulnerability disclosed in 2023 [here]

And here is the 2019 disclosure:

Cisco Vulnerability disclosed in 2019 [here]

The problem seems to trace itself back to 2019 [here], where a significant number of signatures were identical:

Unfortunately, the previous fix does not seem to have worked. At the core is the weak seeding process on the ASA device, and which ends up with the same random numbers. This type of approach is a surprise, as some simple random number tester is fairly easy to setup. Here is the full presentation:

Cracking ECDSA with the same nonce

In ECDSA, Bob creates a random private key (priv), and then a public key from:

pub=priv×G

Next, in order to create a signature for a message of M, he creates a random number (k) and generates the signature of:

The signature is then (r,s) and where r is the x-co-ordinate of the point kG. H(M) is the SHA-256 hash of the message (M), and converted into an integer value.

Now let’s say we have two messages (m1 and m2) and have hashes of:

h1=H(m1)

h2=H(m2)

Now let’s say that Alice signs the messages with the same private key (priv) and the same nonce (k), we can then recover the private key with:

We can also recover the nonce with:

Here is some code which does a discovery of the private key, and the nonce (k) if we use the same nonce value [here]:

import ecdsa
import random
import libnum
import hashlib
import sys
G = ecdsa.SECP256k1.generator
order = G.order()
priv1 = random.randrange(1,order)
 
Public_key = ecdsa.ecdsa.Public_key(G, G * priv1)
x1 = ecdsa.ecdsa.Private_key(Public_key, priv1)
k = random.randrange(1, 2**127)
msg1="Hello"
msg2="Hello1"
if (len(sys.argv)>1):
 msg1=(sys.argv[1])
if (len(sys.argv)>2):
 msg2=(sys.argv[2]) 

h1 = int(hashlib.sha256(msg1.encode()).hexdigest(),base=16)
h2 = int(hashlib.sha256(msg2.encode()).hexdigest(),base=16)
 
sig1 = x1.sign(h1, k)
sig2 = x1.sign(h2, k)
r1,s1 = sig1.r,sig1.s
r2,s2 = sig2.r,sig2.s
valinv = libnum.invmod( r1*(s1-s2),order)
x1rec = (   (s2*h1-s1*h2) * (valinv)) % order
print ("Message 1: ",msg1)
print (f"Signature r={r1}, s={s1}")
print ("\nMessage 2: ",msg2)
print (f"Signature r={r2}, s={s2}")

print ("\nPrivate key",priv1)
print ("\nPrivate recovered ",x1rec)
valinv = libnum.invmod( (s1-s2),order)
k1rec = (   (h1-h2) * valinv) % order
print ("\nK: ",k)
print ("\nK recovered ",k1rec)

A sample run is [here]:

Message 1:  hello
Signature r=16163824871702315365636544754327339671279830383115616072776286071644348532176, s=78942102071383249892109282228339664393041099900407940222266026023142592864884
Message 2:  hello1
Signature r=16163824871702315365636544754327339671279830383115616072776286071644348532176, s=83502523167965149244641473202679268630845178075816922294718909855670078364206
Private key 6542179820561127199468453109220159836323733777364616770035873205004743487369
Private recovered  6542179820561127199468453109220159836323733777364616770035873205004743487369
K:  109308891778201478280270581205739604663
K recovered  109308891778201478280270581205739604663

Conclusion

There’s some sloppy work here on the Cisco ASA device, and where there has been a complete lack of testing for the generation of random numbers.