Skip to content Skip to navigation

Mining Your Rs and Ss (Crypto 500)

Category: 

[To try to solve the task see an attachment below the writeup]

For this particular task we've been given some sort of CA to issue user certificates and authentication part to verify issued user certificate using SSL handshake. The main purpose according to the message provided after authentication is to login with certificate issued to the user named admin. There is no sense telling that one can not do this in ordinary way by requesting it from CA provided.

For some background information we issue three user certificates with random namesn (say N1, N2, N3) and download CA certificate provided. Examination of certificates shows, that ECDSA algorithm is used with curve sect283k1 for certificate signature by CA and curve secp384r1 for user auhentication purposes. After taking a look at the signatures of user certificates one can notice that the first part of signatures, corresponding to r value in ECDSA signature (r, s), is the same, which means that CA is using a very weak RNG, outputting the the same value any time:

openssl asn1parse -in N1.pem -dump -offset 402
    0:d=0  hl=2 l=   7 prim: OBJECT            :ecdsa-with-SHA1
    9:d=0  hl=2 l=  79 prim: BIT STRING        
      0000 - 00 30 4c 02 24 00 fc b5-1f 21 1f ad 7c 90 2b a8   .0L.$....!..|.+.
      0010 - 20 20 e6 52 d6 93 ef d3-38 06 46 87 32 06 06 b8     .R....8.F.2...
      0020 - 8a 40 3a 31 a9 26 8f 27-5e 02 24 00 8a 8a 67 80   .@:1.&.'^.$...g.
      0030 - ed 0e 21 c4 52 80 58 83-68 a7 ce fc 29 76 a6 ee   ..!.R.X.h...)v..
      0040 - ac b5 07 83 7c dc 09 a3-bc 30 29 8c 0e f1 a2      ....|....0)....

openssl asn1parse -in N2.pem -dump -offset 403
    0:d=0  hl=2 l=   7 prim: OBJECT            :ecdsa-with-SHA1
    9:d=0  hl=2 l=  79 prim: BIT STRING        
      0000 - 00 30 4c 02 24 00 fc b5-1f 21 1f ad 7c 90 2b a8   .0L.$....!..|.+.
      0010 - 20 20 e6 52 d6 93 ef d3-38 06 46 87 32 06 06 b8     .R....8.F.2...
      0020 - 8a 40 3a 31 a9 26 8f 27-5e 02 24 00 a7 71 0d e2   .@:1.&.'^.$..q..
      0030 - a4 1b 16 c6 62 89 cb de-2e 5c ed 1e fc 50 43 8a   ....b....\...PC.
      0040 - c2 a1 69 2e 18 90 6c 7b-5f 22 4e 3a 72 a2 af      ..i...l{_"N:r..

openssl asn1parse -in N3.pem -dump -offset 405
    0:d=0  hl=2 l=   7 prim: OBJECT            :ecdsa-with-SHA1
    9:d=0  hl=2 l=  79 prim: BIT STRING        
      0000 - 00 30 4c 02 24 00 fc b5-1f 21 1f ad 7c 90 2b a8   .0L.$....!..|.+.
      0010 - 20 20 e6 52 d6 93 ef d3-38 06 46 87 32 06 06 b8     .R....8.F.2...
      0020 - 8a 40 3a 31 a9 26 8f 27-5e 02 24 01 31 ec 40 94   .@:1.&.'^.$.1.@.
      0030 - cd cf 43 95 77 90 7f 38-e8 93 47 8c d6 bd 6f ea   ..C.w..8..G...o.
      0040 - e0 fb 91 f0 e9 83 a9 1b-a2 bd 7b e2 f8 3e ac      ..........{..>. 

Using a weak RNG in ECDSA means that signer's private key can be recovered. An attack to such realization of signature can be deviced in a minute or simply found here (http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html).

To make an attack we first need to get the data being signed. To do it we use a bit of openssl magic:

openssl asn1parse -in N1.pem -dump -offset 402
    0:d=0  hl=2 l=   7 prim: OBJECT            :ecdsa-with-SHA1
    9:d=0  hl=2 l=  79 prim: BIT STRING        
      0000 - 00 30 4c 02 24 00 fc b5-1f 21 1f ad 7c 90 2b a8   .0L.$....!..|.+.
      0010 - 20 20 e6 52 d6 93 ef d3-38 06 46 87 32 06 06 b8     .R....8.F.2...
      0020 - 8a 40 3a 31 a9 26 8f 27-5e 02 24 00 8a 8a 67 80   .@:1.&.'^.$...g.
      0030 - ed 0e 21 c4 52 80 58 83-68 a7 ce fc 29 76 a6 ee   ..!.R.X.h...)v..
      0040 - ac b5 07 83 7c dc 09 a3-bc 30 29 8c 0e f1 a2      ....|....0)....

openssl asn1parse -in N2.pem -dump -offset 403
    0:d=0  hl=2 l=   7 prim: OBJECT            :ecdsa-with-SHA1
    9:d=0  hl=2 l=  79 prim: BIT STRING        
      0000 - 00 30 4c 02 24 00 fc b5-1f 21 1f ad 7c 90 2b a8   .0L.$....!..|.+.
      0010 - 20 20 e6 52 d6 93 ef d3-38 06 46 87 32 06 06 b8     .R....8.F.2...
      0020 - 8a 40 3a 31 a9 26 8f 27-5e 02 24 00 a7 71 0d e2   .@:1.&.'^.$..q..
      0030 - a4 1b 16 c6 62 89 cb de-2e 5c ed 1e fc 50 43 8a   ....b....\...PC.
      0040 - c2 a1 69 2e 18 90 6c 7b-5f 22 4e 3a 72 a2 af      ..i...l{_"N:r..

openssl asn1parse -in N3.pem -dump -offset 405
    0:d=0  hl=2 l=   7 prim: OBJECT            :ecdsa-with-SHA1
    9:d=0  hl=2 l=  79 prim: BIT STRING        
      0000 - 00 30 4c 02 24 00 fc b5-1f 21 1f ad 7c 90 2b a8   .0L.$....!..|.+.
      0010 - 20 20 e6 52 d6 93 ef d3-38 06 46 87 32 06 06 b8     .R....8.F.2...
      0020 - 8a 40 3a 31 a9 26 8f 27-5e 02 24 01 31 ec 40 94   .@:1.&.'^.$.1.@.
      0030 - cd cf 43 95 77 90 7f 38-e8 93 47 8c d6 bd 6f ea   ..C.w..8..G...o.
      0040 - e0 fb 91 f0 e9 83 a9 1b-a2 bd 7b e2 f8 3e ac      ..........{..>.

So data being signed is the hash of certbody:

openssl dgst -sha1 N1certbody
SHA1(N1certbody)= 4e2e395cfa217aada0173f0fa8b241f7935ee075
openssl dgst -sha1 N2certbody
SHA1(N2certbody)= c0a7730b7195e788c2668241c4c05b4999e4177b
openssl dgst -sha1 N3certbody
SHA1(N3certbody)= 9cd1d8b1129b6eca8670e84f3897ec810aa96854 

To recover private key of CA we use this sage script (private key is calculated twice for different certificate pairs to confirm our hypotheses):

#http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html

# SECT283K1 Curve Parameters
# p -- is a large prime, and the order of the subgroup generated by G # http://tools.ietf.org/html/draft-campagna-suitee-02
p =0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE9AE2ED07577265DFF7F94451E061E163C61 # http://tools.ietf.org/html/draft-campagna-suitee-02
# r -- part of signature (r, s)
r =0x00FCB51F211FAD7C902BA82020E652D693EFD338064687320606B88A403A31A9268F275E
# signatures
s1=0x00A7710DE2A41B16C66289CBDE2E5CED1EFC50438AC2A1692E18906C7B5F224E3A72A2AF
s2=0x008A8A6780ED0E21C45280588368A7CEFC2976A6EEACB507837CDC09A3BC30298C0EF1A2
s3=0x0131EC4094CDCF439577907F38E893478CD6BD6FEAE0FB91F0E983A91BA2BD7BE2F83EAC
# data signed
z1=0xc0a7730b7195e788c2668241c4c05b4999e4177b
z2=0x4e2e395cfa217aada0173f0fa8b241f7935ee075
z3=0x9cd1d8b1129b6eca8670e84f3897ec810aa96854

K = GF(p)

K((z1*s2 - z2*s1)/(r*(s1-s2)))
K((z1*s3 - z3*s1)/(r*(s1-s3)))

 The result of script is private key of CA:

>>> hex(1779322126191052087653210276489675744619364270759949965827494010645248553173825795038)
'0xea797dcbac1c6199f753e6253b220a8449812b05af20630c310f33742810fe48e2b3deL'

Now it's time for some more openssl magic to make PEM of CA private key. First extract CA public key from certificate:

openssl x509 -noout -in cacert.pem -pubkey | openssl asn1parse -dump
    0:d=0  hl=2 l=  94 cons: SEQUENCE          
    2:d=1  hl=2 l=  16 cons: SEQUENCE          
    4:d=2  hl=2 l=   7 prim: OBJECT            :id-ecPublicKey
   13:d=2  hl=2 l=   5 prim: OBJECT            :sect283k1
   20:d=1  hl=2 l=  74 prim: BIT STRING        
      0000 - 00 04 00 6c cb 96 b0 74-82 81 d3 8a 90 f4 99 40   ...l...t.......@
      0010 - e7 9d b5 4f 4b d4 eb 91-91 e5 a4 94 db 1f d4 e1   ...OK...........
      0020 - 44 85 27 d3 18 af 01 7d-c8 21 0a 96 8f 1c eb 88   D.'....}.!......
      0030 - 27 a5 2a 1b 64 51 b0 7d-93 70 77 a1 bf af 08 08   '.*.dQ.}.pw.....
      0040 - f9 99 cc 71 82 e4 bd 19-50 72                     ...q....Pr

So public key value in hex is:

0004006ccb96b0748281d38a90f49940e79db54f4bd4eb9191e5a494db1fd4e1448527d318af017dc8210a968f1ceb8827a52a1b6451b07d937077a1bfaf0808f999cc7182e4bd195072

Now generate PEM of private key for given curve:

openssl ecparam -out ec_key.pem -name sect283k1 -genkey

View what there is:

openssl pkey -inform PEM -in ec_key.pem -text
-----BEGIN PRIVATE KEY-----
MIGPAgEAMBAGByqGSM49AgEGBSuBBAAQBHgwdgIBAQQjicjkPAvY6jCO8CWcGUOg
OBZcNtdp+detONZg61TTLhBZ0tKhTANKAAQHu2G42k56qQbyq6o6hNImkzu0mK5p
wEtY6qGerVbTeW2ZDHIFEo9YHkqNNzCHJx55p3/CkVO1njtwHS1ot+ogUdGVA84L
wOY=
-----END PRIVATE KEY-----
Private-Key: (281 bit)
priv:
    00:89:c8:e4:3c:0b:d8:ea:30:8e:f0:25:9c:19:43:
    a0:38:16:5c:36:d7:69:f9:d7:ad:38:d6:60:eb:54:
    d3:2e:10:59:d2:d2
pub: 
    04:07:bb:61:b8:da:4e:7a:a9:06:f2:ab:aa:3a:84:
    d2:26:93:3b:b4:98:ae:69:c0:4b:58:ea:a1:9e:ad:
    56:d3:79:6d:99:0c:72:05:12:8f:58:1e:4a:8d:37:
    30:87:27:1e:79:a7:7f:c2:91:53:b5:9e:3b:70:1d:
    2d:68:b7:ea:20:51:d1:95:03:ce:0b:c0:e6
ASN1 OID: sect283k1

Dump ec_key.pem in DER encoding as hex string:

openssl ec -in ec_key.pem -outform DER| xxd -p
read EC key
writing EC key
307f020101042389c8e43c0bd8ea308ef0259c1943a038165c36d769f9d7
ad38d660eb54d32e1059d2d2a00706052b81040010a14c034a000407bb61
b8da4e7aa906f2abaa3a84d226933bb498ae69c04b58eaa19ead56d3796d
990c7205128f581e4a8d373087271e79a77fc29153b59e3b701d2d68b7ea
2051d19503ce0bc0e6 

Replace private and public keys with the recovered ones of CA and generate CA's private key in PEM:

echo \
307f0201010423ea797dcbac1c6199f753e6253b220a8449812b05af2063\
0c310f33742810fe48e2b3dea00706052b81040010a14c034a0004006ccb\
96b0748281d38a90f49940e79db54f4bd4eb9191e5a494db1fd4e1448527\
d318af017dc8210a968f1ceb8827a52a1b6451b07d937077a1bfaf0808f9\
99cc7182e4bd195072 | xxd -r -p - | openssl ec -inform der -out cakey.pem -outform pem 

Prepare environment of your own CA: 

mkdir myCA
cp cacert.pem myCA/
cp cakey.pem myCA/
cd myCA
mkdir -p demoCA/newcerts
cat /dev/null demoCA/index.txt
echo -n "00" > demoCA/serial

Now make certificate request with "admin" in the CN field:

openssl ecparam -out admin_key.pem -name secp384r1 -genkey
openssl req -new -nodes -key admin_key.pem -outform pem -subj /C=IR/ST=Tehran/O=NoLoginPage\ Co./CN=admin/ -noout -text

Sign the request to get certificate:

openssl ca -cert cacert.pem -keyfile cakey.pem -in admin_cert.req -out admin_cert.pem

Export admin certificate and private key to p12:

openssl pkcs12 -export -in admin_cert.pem -inkey admin_key.pem -out admin_cert.p12 

Import certificate to Firefox. Login to authentication part:

VoilĂ ! Take you flag!

 

Attachments: