dimanche 22 octobre 2017

CTF Writeup: Ugly Duckling

Ugly Duckling

Given Problem

The problem is given as follows:

$ cat input.txt

Pour réussir ce challenge tu dois envoyer la signature valide du message "Please give me the flag" en utilisant le même format de signature que ci-dessous :

-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEpuXtxRVM66Bs0wooq288G3VXUHlr
bFTkMdbFM+SVYaFySfyUggFwTNKiDuTayOpLQNF6ypapU3eXBnIkWdcqSw==
-----END PUBLIC KEY-----

Texte   ECDSA signature (der format)
'A digital signature is an elec'        MEUCIDNzKttS2wQHNwzVXyImvgtfsfo3RunkXx51nzkJky4hAiEAqxs7FnifkxpkmgT/TKuArbkQfxDrpNrWgRhjw2v9XYY=
'tronic analogue of a written s'        MEUCIC+ZtRvik6shfweDx7pltMU7+hWz/DZIlbuj3JBTE//qAiEA2vbJh18ywznfxsr4s1EBqI6F3nvH226WmwR8TfVsMEQ=
'ignature; the digital signatur'        MEUCIQDYOVf/wraAaEU2O81ECbnROj9H0KuRbf0fl/LocEKPFQIgbu4fV5T80A3tnYSi+eCYR89q7C2iZKKlImf/SywrMxg=
'e can be used to provide assur'        MEYCIQDQF2s2MvGiYzFGke39SCTEjC8Q95pq8PzLw1ZuqxWSzAIhAJzRcgwZFV7etGoMS6GyVmuSAhSX5c0kkJDT2fbZdHqZ
'ance that the claimed signator'        MEQCIGwB5PAkCYjy4sySscUbP2O24xQ0eXTOzhEnCU5d7v4rAiAfqBgrGVL5jWC49rY051aF2EH2pEP5TUFCx305hgXDkw==
'y signed the information. In a'        MEUCIArXFq3NLflM1aG5BJU9V7UTt464jLjZ4DXkPpccBW73AiEAs/tjla3KvobfedoELIXyrrppG+G0sAaIvLYMnBQq6vc=
'ddition, a digital signature m'        MEYCIQC6zHS5/+pfZlN2jzWVZBW6VNlA43exr61hQlL1BACVggIhAJt2ar7DZDJ/vXAy5WdRqWetyLAWUWWbT7bTN4bm+GK3
'ay be used to detect whether o'        MEUCIQC8dTE25xekSpbyjLBWcrl440BJxEmrStIU7noKyj8ecAIgNFyjIz0AWNIZ+ZbRukOXm/Z07UuMBUohddqmHqbFBiw=
'r not the information was modi'        MEQCIEw5Ar8j7/msmmDr1kqqUwzvIs/Vnga/kD3OLE9sK3cYAiBGfT0gehy5aA9mE5FyBethtFykxLm3A1H2KeKWkseZLQ==
'fied after it was signed (i.e.'        MEUCIFjR6vlS/D+nFcZtBXBgRN1XQHHMX3CZ5FSbfVi3a5EDAiEAk386UuIa+NfFHVkdc0UqrsNshf5qvJtw70Yf1RaolPg=
', to detect the integrity of t'        MEUCIQCmGscR5TXMmdEd5pAa/mXL4ScZlg0eWx56P9dBG2V7PwIgDkazr6fwr6YBDbABw6xMvPy2sGmp/wHNyZvUdMBw/b8=
'he signed data). These assuran'        MEQCIDzdi89bc02mdxTxSo7tA8dmr3Xl0PrxugSy7KO93NR6AiArE3Hy+NPD3AYEuZTQy7vjzHVSLK0YsbEoPLZRZnI3fA==
'ces may be obtained whether th'        MEQCICLL5y+sABYiJPW0TunEwvvHo0er7kFYgknxlqA1HoEjAiA5KohKdl1cxUg3GPa/aoiRqXoOHSF/4NdXxffYV4mPdg==
'e data was received in a trans'        MEUCICRfjlf/nIOMEbSzeVL/5hy3M/dC/jqKjHf3AiWYD1MWAiEA1J8A6YnQMimn6ZyE7b92DdFBSmwUC7+qomPHYx8kwkc=
'mission or retrieved from stor'        MEQCIG5Kuc7MbAlWczmSQpp/N8SljidJXRZexQ5iko6VVDL6AiAM07//x/OPcoLzcwEu7VtD/l37DAbapNyJ/WbRvrAdHg==
'age. A properly implemented di'        MEUCIFbd+3sIcEKkWdg+fkaCz1+bzXVjHTcer02nnf2a5XZdAiEA00gEkt6V7NVmqXMTrPXDDKzBKmAnXvAxF/RnRh/Tpv4=
'gital signature algorithm that'        MEYCIQDK4vyVFYNrPCpA5ET/uU5qD31h11Xu4dSt82zNg/reqwIhAMud2+okRJjkmbocXLw/oBOSRnFjokBRV3V5hnSmO0T1
' meets the requirements of thi'        MEQCIDDUeIXikKGfrGgiUvPqqpEizbNmaedtWlyXIvZwj/D4AiAG9dubFytj5Njqxf9zh/ZKVmQCtIoj0LGp3W1VvpMa/w==
's Standard can provide these s'        MEQCIE7UTRM8TVjQHMS0KsCEMHVii8Ulaw/Bf8SV2668QPeAAiAHZAzWYpE7BcqJ1gNN8hCv1gX4ybiGDDvpPg6C1JnP2A==
'ervices. A digital signature a'        MEUCIHWoQIQYAy3gc2VOQCsmyGKW1X5pPt79ORThS2I9d/pJAiEA0HkvYzawmZoR9b6ZoxCocuv9sD+8lrzQ8O9hGSB3P9E=
'lgorithm includes a signature '        MEUCIDsBNIHvhQ5+T+ndF/hQfZFMPaen107691pH8W9mun29AiEAjmjEqHKGdx2pb8wyvMC9dnKWsP/7YLdd2k1z+s6BkKs=
'generation process and a signa'        MEQCIAEff3DMImrnEEppqNz9qfup7Av24NKYhLsyeq+ApmObAiB7yC4dmPsZW16I+h6wQMG87Q2dajDzjsZD/kwMEGuH6A==
'ture verification process. A s'        MEUCIDzdi89bc02mdxTxSo7tA8dmr3Xl0PrxugSy7KO93NR6AiEAkhWDrap8G1x5mMSXJtdeJ56hx61G7sg4ojS+i4eabF4=
'ignatory uses the generation p'        MEUCIQDfhyzEKt8Qurm4LK4FtuRnPTp1KNyf6fXyYUNDRHXbOwIgMEog89tFr1fWWxx8P2unXoUBDu/SAJiE/40T1Gl2KlM=
'rocess to generate a digital s'        MEYCIQCQ9GixXBtt+joG5D3c1ZVoj2aCIGjxw22OGHZNR/GpYgIhAJwWR2Nkr0Ms+hQF/dcWg2fNBqZmBI9m4Br/WmwATlPV
'ignature on data; a verifier u'        MEQCICCETeP/NzX32baDeo+mbFq0YCPSlaEJZDiur5gZ15ZuAiBqgCmVSjtXK2NL5SoVmIdXUZvNrbU6gnKW9gaF59vpoQ==
'ses the verification process t'        MEQCIAWqoBkB5OZmos3tVkNkLyd30cHOB//Buo9WkkDme5+jAiBtnnaac51pCOtAWJLbrfYoJJya0FSiNVy8dcctZ5242A==
'o verify the authenticity of t'        MEYCIQCuLA1pnnD8F96Ru1A+MJKEzNpEKeHpLo84FBysXvREhgIhAJcvUWlXDioZG06CeisZWoC/nhFISm84Q4gaSPYnCiLt
'he signature. Each signatory '         MEYCIQD4uTDW+H3EGJLdrONv96Si1xwFuGpGbJXJRbCEq9Q9XQIhAKaMvng/m7yEt4BVTWiUHijBkKD8QFlgRqe7s37PKWWn
'has a public and private key a'        MEUCIQDB74Y+I95JejE5sscxrF3/pczW9DuqYkOXUT7cHY7SLQIgBgoM2cELtLMxQZ2UPOT6hO4hD3PMbA5WesI4i+AtgLI=
'nd is the owner of that key pa'        MEYCIQCT9iPHDQFb+O7koDuizf/FY9XrNK96VIdOdbcAwdIERAIhAOADAcyFiarRaxDNPu/HuZZvC+/7Trz/iiaEsNWWPM3w
'ir. As shown in Figure 1, the '        MEYCIQCw+GJl5FfDbU0nec8CL70LVegRA70xXWJCaQVhdtCjLgIhALbEdgRtmMWCm2rZAxAhf4CqAZF71Zzmq2W0yXPnb17X
'private key is used in the sig'        MEYCIQDkCroMVPLLkjrqfL3jiJxN3rGeJNZYnbUMgTJFb7L/VAIhAJXWWkZO5BS5c7Xga/BVXtrQ2HLaHB8UEQlOzj2T2lIN
'nature generation process. The'        MEUCIFw9n2BPBX+/xhliTEmTNxGekMEAnjhUCcfPatkQr7V7AiEAh1Bvdkf2DYO58gKOAevXX5Y4GJxNXtD8UF8p6gS5QuI=
' key pair owner is the only en'        MEYCIQCPuwz1Q+JM6x6WrlpaDzjutYmJ0vo7g/F2+y+T1awaAwIhAPrkjswme2TYOWU3umS39m/y3oT3uaKilEi9tnUeIsWG
'tity that is authorized to use'        MEUCIBxken6kPgmDpzrcZHa6vUSRfJNjikkJQ9rDiMRS9Mr4AiEAszoYsEzIXHawTKcKoT1XlCbro+sujqI9OUrOLMWxjkY=
' the private key to generate d'        MEUCIQCZ1AFzdZIdb9lfg+ptueWTR42/atSB0+r0szxT9whUOwIgWEgroIoIoMJqo5LRZZYqZIFnQERTILBrQ8XrWlD/Veg=
'igital signatures. In order to'        MEYCIQCcXN3ks4DC/TLmBT9votOfWJ4/8jUKunhRb3w5VU1XSwIhANY8bOOCKbHA7O8K/NjFpjmK13IYLkUbHC2aCQcatBvf
' prevent other entities from c'        MEYCIQCYrwIA5TvvIEdQptVGhkeSnqZ38ARgU1oxMbyZZ3D5eAIhAJpzeQLj1eUr6Nhc1NGoxQFOmgGe7TpYiR/ALCAhuO8T
'laiming to be the key pair own'        MEUCIH3pfl2Sy9GP8jpiAD2IcgJ95vQC6vJ/Sty+PnTMBwTHAiEAp0+HoILnxuEEGBFLoEXsaZWSWCKCZKmxK/Upod2rsKc=
'er and using the private key t'        MEYCIQDluqTTkQnKwSqjJUOU4ZD2jvpyCoR/9toHWS0x5GML4gIhAOtpIx7LLgDwpAjLqh3BIJYuyh9uqHMvFRxju5kNJQ1R
'o generate fraudulent signatur'        MEUCIBzgpFtPo1uoUbqry+z9hOJCmd6TZmJzhtxkUA613F9OAiEAiqY/clKDxaV58YbCpiQHH68OLkFwPwhpivJIgSj+qg8=
'es, the private key must remai'        MEUCIQCjvjNiTVCbUCchpfJICBswkahOfWVnHy6yGnW6QeHurQIgM1Hd7FrFKSHCabCuY/8KH/c92q4vbqQG3HzjX45UX3U=
'n secret. The approved digital'        MEUCIQC3rNA018ZwHwLEU4y2y9HVk3UXMEPd3QejYFxk/9aoJAIgZN6M5YsspS1nsgMkFO+lCwQdlbKBTfD5H6HvS+d7j8U=
' signature algorithms are desi'        MEQCIDcmhg84twVDSsEHjeBGMwO79QtnK4r9fEM8UJuGYpzQAiAvdVhfIVBD3ywk3nPxNr/ch5eCCI5rU5cByjQOGyw70g==
'gned to prevent an adversary w'        MEUCIBhZ9OhNnarubB1yj+GZJMryhgT9i6zotYw4zjOeb7npAiEA2q647rZuES2DIfrQVIu104k87PJUFyEs/cSYAEYE2cc=
'ho does not know the signatory'        MEUCIGZDqeSi6Z7EYTZbqaeMpUkLOkOrIL9xH9hJAmHjyHiiAiEAnvXdmluEY1tFjsNobGmIaao7NvYf2CtelrsSC3xRnR4=

For non french speakers, this means we need to forge a signature for the string "Please give me the flag", using the same format as the bunch of valid signatures below.

Introduction to ECC and ECDSA

ECC (Elliptic Curve Cryptography) works by manipulating points on a curve. These points are canonically defined by their coordinates (x,y). Traditionally we understand the curve as the 2D plane over the real numbers, but real numbers are not suitable for cryptography. Thankfully, ECC works on various kind of number fields; for cryptography, instead of the real numbers, we may chose to work in the field of integers modulo p, where p is a prime number.

The points (x,y) on the curve form a group, meaning we can "add" points together, and also multiply a point by an integer (which means repeatedly adding the point with itself). The definition of point addition is a bit weird, and involves geometry on the curve. For now, let's just assume that we know a way to perform these two operations on points of the curve.

The security of the scheme lies on the difficulty of computing the logarithm of a point. I.e., given a point P, and a large integer k, we can easily compute the point Q = k⋅P. But given Q and P, there is no fast way to find k. (If k is small, we can use, for instance, Daniel Shanks's baby-step giant-step algorithm)

You can check Wikipedia for the definition of the the Elliptic Curve Digital Signature Algorithm, ECDSA1. The public parameters are: the curve definition (that we need to perform addition and multiplication of points), and a base curve point G that generates a subgroup of order n. Fortunately, when using standard curves, a good generator point has been precomputed for us, along with its order n, which should be large.

Alice, the signer, then picks a private key, which is an integer d. Her public key becomes the curve point Q = d⋅P.

Public key extraction

We can extract the data of the public key like this:

$ openssl ec -pubin -noout -text < input.txt
read EC key
Private-Key: (256 bit)
pub: 
    04:a6:e5:ed:c5:15:4c:eb:a0:6c:d3:0a:28:ab:6f:
    3c:1b:75:57:50:79:6b:6c:54:e4:31:d6:c5:33:e4:
    95:61:a1:72:49:fc:94:82:01:70:4c:d2:a2:0e:e4:
    da:c8:ea:4b:40:d1:7a:ca:96:a9:53:77:97:06:72:
    24:59:d7:2a:4b
ASN1 OID: prime256v1
NIST CURVE: P-256

This indicates the standard NIST curve (P-256) is being used. Thankfully, there is an existing Haskell package, eccrypto, that implements operations on this curve.

Understanding the format of the public key took a little bit of googling. RFC 54802 states that the public key (a point on a curve) is stored with a first byte, indicating uncompressed (0x04) or compressed (0x02 or 0x03) representation. For the uncompressed representation, that we have here, we simply have the x-coordinate followed by the y-coordinate. The P-256 curve is defined over the field of integers modulo a 256-bit prime, so each coordinate is 256 bits (64 bytes) long.

The rfc does not specify the endianness of these points, but like most these formats, i will assume network endinanness here. So our public point is:

pub_x = 0xa6e5edc5154ceba06cd30a28ab6f3c1b755750796b6c54e431d6c533e49561a1
pub_y = 0x7249fc948201704cd2a20ee4dac8ea4b40d17aca96a953779706722459d72a4b

Signatures extraction

Each line is obviously base64. Could it be a standard signature format in PEM representation ? let's ask openssl, using the first signature as a sample:

openssl asn1parse <<< MEUCIDNzKttS2wQHNwzVXyImvgtfsfo3RunkXx51nzkJky4hAiEAqxs7FnifkxpkmgT/TKuArbkQfxDrpNrWgRhjw2v9XYY=
    0:d=0  hl=2 l=  69 cons: SEQUENCE          
    2:d=1  hl=2 l=  32 prim: INTEGER           :33732ADB52DB0407370CD55F2226BE0B5FB1FA3746E9E45F1E759F3909932E21
   36:d=1  hl=2 l=  33 prim: INTEGER           :AB1B3B16789F931A649A04FF4CAB80ADB9107F10EBA4DAD6811863C36BFD5D86

Two 256-bit integers. Wikipedia told us that an ECDSA signature is made of two integers, r and s, in the group of integers modulo k, the order of the elliptic curve subgroup.

Wikipedia also tells us that a common failure for ECDSA is insufficient randomness in the selection of the nonce k. If a collision occurs (the same k is used to sign two different messages), then it is obvious from the signatures (they will have the same r, but not the same s, and knowledge of this information can allow us to retrieve the k, then in turn retrieve the private key d.

With only shell scripting, it is easy enough to test this possibility:

$ for sig in $(cut -f2 signatures.txt); do openssl asn1parse <<< $sig; done |grep INTEGER |sort |uniq -c |egrep '^\s*2'
2     2:d=1  hl=2 l=  32 prim: INTEGER           :3CDD8BCF5B734DA67714F14A8EED03C766AF75E5D0FAF1BA04B2ECA3BDDCD47A

Bingo: one of the values is repeated twice. Let's find the culprits:

$ for sig in $(cut -f2 signatures.txt); do echo $sig; openssl asn1parse <<< $sig; done |grep -B2 3CDD8BCF5B734DA6
MEQCIDzdi89bc02mdxTxSo7tA8dmr3Xl0PrxugSy7KO93NR6AiArE3Hy+NPD3AYEuZTQy7vjzHVSLK0YsbEoPLZRZnI3fA==
    0:d=0  hl=2 l=  68 cons: SEQUENCE          
    2:d=1  hl=2 l=  32 prim: INTEGER           :3CDD8BCF5B734DA67714F14A8EED03C766AF75E5D0FAF1BA04B2ECA3BDDCD47A
--
MEUCIDzdi89bc02mdxTxSo7tA8dmr3Xl0PrxugSy7KO93NR6AiEAkhWDrap8G1x5mMSXJtdeJ56hx61G7sg4ojS+i4eabF4=
    0:d=0  hl=2 l=  69 cons: SEQUENCE          
    2:d=1  hl=2 l=  32 prim: INTEGER           :3CDD8BCF5B734DA67714F14A8EED03C766AF75E5D0FAF1BA04B2ECA3BDDCD47A

So the signatures for these two messages are colliding:

'he signed data). These assuran'        MEQCIDzdi89bc02mdxTxSo7tA8dmr3Xl0PrxugSy7KO93NR6AiArE3Hy+NPD3AYEuZTQy7vjzHVSLK0YsbEoPLZRZnI3fA==
'ture verification process. A s'        MEUCIDzdi89bc02mdxTxSo7tA8dmr3Xl0PrxugSy7KO93NR6AiEAkhWDrap8G1x5mMSXJtdeJ56hx61G7sg4ojS+i4eabF4=
                                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Funnily enough, you can even tell that something is fishy through the base64, with the abnormal repetition over almost half of the signature.

Recovering the secret nonce and private key

As Wikipedia explains, from a pair of colliding signatures (r,s) and (r,s'), we can recover k by computing

k = (s - s') / (z - z')

Recall that all these numbers are elements of the integers modulo n, where n is the order of the generated subgroup on the curve. The z and z' are computed from the hash of the message to be signed.

Here we hit our first problem: nowhere it is specified which hash algorithm to use. But since the subgroup order is a 256-bit number, it seems natural to use a hash function with a 256-bit output, so SHA-256 is our prime candidate.

We can quickly test this hypothesis by doing a signature verification. Let us implement the verification algorithm in Haskell, and test it on our sample message (i'm only showing the core parts, the full code can be found at the end of this article.

verify :: Parameters -> Pubkey -> Signature -> Message -> Either String ()
verify (ec, g, n) pub (r,s) m = do
    not (ison ec pub) ?? "public key not on curve"
    zero pub ?? "public key is zero"
    (not.zero) (pmul ec pub n) ?? "public key not in subgroup"
    not ((r `within` (0,n)) && (s `within` (0,n))) ?? "signature out of bounds"
    let z = expand (hash m)
        w = inv n s
        (u1,u2) = ((z*w) `mod` n, (r*w) `mod` n)
        o = padd ec (pmul ec g u1) (pmul ec pub u2)
    zero o ?? "validation point was zero"
    let (x1,_) = affine ec o
    ((x1 `mod` n) /= r) ?? "signature incorrect"


curve = standard p256
pub = ECPp 0xa6e5edc5154ceba06cd30a28ab6f3c1b755750796b6c54e431d6c533e49561a1 0x7249fc948201704cd2a20ee4dac8ea4b40d17aca96a953779706722459d72a4b 1
r = 0x3CDD8BCF5B734DA67714F14A8EED03C766AF75E5D0FAF1BA04B2ECA3BDDCD47A
s1 = 0x2B1371F2F8D3C3DC0604B994D0CBBBE3CC75522CAD18B1B1283CB6516672377C
m1 = BS8.pack "he signed data). These assuran"
s2 = 0x921583ADAA7C1B5C7998C49726D75E279EA1C7AD46EEC838A234BE8B879A6C5E
m2 = BS8.pack "ture verification process. A s"



> verify curve pub (r,s1) m1
True
> verify curve pub (r,s2) m2
True

Incredibly, it works, both signatures check out. After testing that fake signatures fail too (for instance by swapping m1 and m2), we can now be sure that our choice of hash function was correct, and that everything is working correctly.

Let us then recover the nonce:

crack :: Parameters -> Pubkey -> (Message, Signature) -> (Message, Signature) -> Either String (Nonce, Privkey)
crack p@(ec, g, n) pub (m,(r,s)) (m', (r',s')) = do
    (r /= r') ?? "Sorry, signatures must have identical k for attack to work"
    verify p pub (r,s) m
    verify p pub (r,s') m'
    let (z, z') = (expand (hash m), expand (hash m'))
        k = (((z - z') `mod` n) * inv n ((s - s') `mod` n)) `mod` n
        d = (((s*k - z) `mod` n) * inv n r) `mod` n
    return (k,d)

> crack curve pub (m1, (r,s1)) (m2, (r,s2))
Right (4242,103872287559379399914744843410101948027129342521289341348401895871744811275392)
    

The attack succeeded, and we recovered the nonce k along the private key d. We can see that the k is way too small; With minimal effort, we could have also recovered it from a single signature, by using the baby-step giant-step algorithm to compute the discrete logarithm of r. Or even bruteforce, with such a small k.

Forging the signature

Translating the signature algorithm to Haskell:

sign :: Parameters -> Privkey -> Message -> IO Signature
sign p@(_,_,n) d m = go where
    z = expand (hash m)
    sign' = signDeterministic p d z
    go = do
        k <- randomRIO (1,n-1)
        let (r,s) = sign' k
       if r == 0 || s == 0
            then go
            else return (r,s)

signDeterministic :: Parameters -> Privkey -> Integer -> Nonce -> Signature
signDeterministic (ec, g, n) d z k = (r,s) where
    o = pmul ec g k
    (x1,_) = affine ec o
    r = x1 `mod` n
    s = ((z + r*d) * (inv n k)) `mod` n

The main signature algorithm consists of repeatedly choosing random values for k, and perform the deterministic signature algorithm, until the signature suceeds. Separating the deterministic part of the aglorithm allows us to check that we can reproduce the existing signatures correctly:

> signDeterministic curve d (expand (hash m1)) k
(27530209049394021804796111372881947298263230630819314890086433009851116082298,
 19483809031160088219707292315523236671341089479317580677415257951387180480380)

Those are the same values we had for our first colliding signature, so we are indeed able to forge signatures. Now to forge a valid signature for the target message:

> let target = BS8.pack "Please give me the flag"
> signature <- sign curve d target
> signature
(49271142319910802430075384114425720548318215767445215127383189594429821860418,
96491998978165891981048277068100550839827797802373671138054367991983326982329)

And we have a valid signature. All that remains is to put it in the proper format. Thankfully, DER is not that hard. Let's have a look at the DER encoding of the first signature, and compare it with the ASN.1 parser output:

$ openssl asn1parse <<< MEQCIDzdi89bc02mdxTxSo7tA8dmr3Xl0PrxugSy7KO93NR6AiArE3Hy+NPD3AYEuZTQy7vjzHVSLK0YsbEoPLZRZnI3fA== 0:d=0 hl=2 l= 68 cons: SEQUENCE
2:d=1 hl=2 l= 32 prim: INTEGER :3CDD8BCF5B734DA67714F14A8EED03C766AF75E5D0FAF1BA04B2ECA3BDDCD47A 36:d=1 hl=2 l= 32 prim: INTEGER :2B1371F2F8D3C3DC0604B994D0CBBBE3CC75522CAD18B1B1283CB6516672377C

$ base64 -d <<< MEQCIDzdi89bc02mdxTxSo7tA8dmr3Xl0PrxugSy7KO93NR6AiArE3Hy+NPD3AYEuZTQy7vjzHVSLK0YsbEoPLZRZnI3fA== |hexdump -C 00000000 30 44 02 20 3c dd 8b cf 5b 73 4d a6 77 14 f1 4a |0D. <...[sM.w..J| 00000010 8e ed 03 c7 66 af 75 e5 d0 fa f1 ba 04 b2 ec a3 |....f.u.........| 00000020 bd dc d4 7a 02 20 2b 13 71 f2 f8 d3 c3 dc 06 04 |...z. +.q.......| 00000030 b9 94 d0 cb bb e3 cc 75 52 2c ad 18 b1 b1 28 3c |.......uR,....(<| 00000040 b6 51 66 72 37 7c |.Qfr7|| 00000046

DER is a type-length-value encoding. In the hexdump, we can see the tag for SEQUENCE (0x30), followed by a payload of 68 (0x44) bytes. The first element is an INTEGER (0x02) of 32 bytes (0x20), the second element is the same. Since we are not changing the size of the signature, we can simply graft its bytes with the appropriate headers:

wrap :: Signature -> BS.ByteString
wrap (r,s) = B64.encode $ BS.concat [ BS.pack [0x30, 0x44, 0x02, 0x20]
                                    , unexpand r
                                    , BS.pack [0x02, 0x20]
                                    , unexpand s
                                    ]



> wrap signature
"MEQCIHezKnsrkDZKoe28ZjyUecU+V/VZG5jU0OAaPr973u96AiBwB4imIDh7eYCvlwYrchiAADEWNEOGtrR6om1dvsuqTw=="

We submit as a final solution:

'Please give me the flag'   MEQCIHezKnsrkDZKoe28ZjyUecU+V/VZG5jU0OAaPr973u96AiBwB4imIDh7eYCvlwYrchiAADEWNEOGtrR6om1dvsuqTw==

mardi 10 novembre 2015

CTF Writeup : Hack.lu 2015 - checkcheckcheck

Inputs

For this problem, we are given the source code of an authenticated service. We have to login by providing a password, which is then concatenated to a salt, hashed with SHA256, and truncated to 48 bits. The server checks if the hash is correct, using a timing-proof algorithm (the two values are XORed, then all the bits of the result are combined with bitwise OR.

Countrary to usual attack scenarios, the actual salt is hidden from us. However, if the login fails, a stale debugging statement informs us of the difference between the stored hash and the computed hash (though because we do not know the salt, we cannot a priori make use of this information, as we do not know how to compute the hash.)

Vulnerability

The XOR implementation used for the timing-safe comparison is destructive (the first operand is replaced with the result of the XOR.) Furthermore, the order of arguments is reversed when testing the password: instead of overwriting the temporary computed hash, it overwrites the stored hash, which persists across login attempts from the same session (but not across connections - the connection handler loads the stored hash from a file before starting its main loop.)

Formally, a connection starts with a stored hash S=S0, and for every new submitted password pi, the stored hash gets replaced by a new value Si=Si1H(pi)

Solution

The first step is to recover the stored hash. If we submit the same password p twice, we get to observe S2=S1H(p)=S0H(p)H(p)=S0

Once the original hash is observed, the problem reduces to finding a sequence of n passwords pi such that Sn=0

Because XOR is a linear operation, we know that we can solve this problem for any S0 by finding an orthogonal basis for our vector space. That is, as the hash is 48 bits long, we need to find, for every bit position, a sequence of passwords that hashes to all zeros except in this specific position. Once this is determined, we can get to any hash value by combining the basis vectors for the bits we want.

There is an easier way, though. It is enough for us to find a basis such as the i-th vector has a 1 in the i-th bit position, and a 0 in all the previous bit positions. This corresponds to reducing a matrix to upper triangular form. Once we have this basis, we can apply (or not) each of the basis vectors in turn, dynamically adapting to the new result.

We need 48 basis vectors to spawn our 48-dimension output hash. We will use more random vectors, to lower the probability that our random vector set would accidentally be linearily dependant (and thus not a basis)

The solution is thus as such:

  • Connect to the service 100 times, submitting different passwords like dummy00, dummy01, dummy02, etc...
  • For each password, observe the hash difference, and deduce the actual computed hash (because the original stored hash is known)
  • Generate a matrix of bits containing the hashes outputs. This matrix has 100 lines (one per hash) and 48 columns (one per hash bit)
  • Adjunct an identity matrix to this one, then make the left part into an upper triangular matrix, by doing the following for each row:
    • For every bit before the i-th, check if it is 0. If not, xor with the i-th matrix row to make it 0.
    • Ensure that the row has a 1 in its i-th position (if not, drop the row or exchange it with a lower one)
  • Select all the rows corresponding to the 1 bits of the target hash, and xor them together. The 100 rightmost bits (where the identity matrix used to live) indicate which passwords from the random set, xored together, generate the target hash
It only remains to connect to the service, and automatically submit the set of all chosen passwords.

jeudi 14 mai 2015

Un conte d'horreur pour sysadmins

Journal d'un sysadmin bénévole - mercredi 13 mai, 20h

Je suis enfin rentré chez moi après une fructueuse journée de travail. Je m'installe dans mon canapé avec ma tablette, lance mon client ssh, attache mon tmux, dans lequel tourne mon client IRC.

Immédiatement, un détail m'interpelle, un enigmatique message dans le log de mes messages privés: "c'est quoi ce bordel ?"

Je lance /map dans mon client. Urgh. Sur la vingtaine de serveurs, réels ou virtuels, de notre petit réseau IRC privé, seule une poignée subsiste. Le site faisait tourner les services est hors circuit. Les admins responsables sont injoignables. Je peste intérieurement. La dernière fois que c'était arrivé, j'avais hurlé pour qu'un backup soit prêt a prendre le relais, ça n'a pas été fait. Tant pis.

En attendant, et ne sachant pas combien de temps durera la panne, je décide de préparer mon site a prendre le relais; je lance la compilation d'Atheme, puis joue un peu avec ma tablette en attendant.

mercredi 13 mai, 21h

Je retourne sur mon client SSH pour vérifier la progression de la compilation. Tiens, il s'est déconnecté. Je le relance. Il refuse de se connecter... plus de réseau ? je visite un site web au hasard, ça fonctionne. Bizarre.

Je vais chercher mon laptop sous windows. J'ouvre un client SSH. Le verdict est sans appel:

Cannot open session: PTY allocation failed.

Allons bon.. voila qui est mauvais. Je vais chercher mon eeePC sous gentoo, et lance la connexion ssh. Le shell se lance, effectivement sans PTY, donc sans prompt, sans couleurs, sans readline, rien. MAIS, il fonctionne. Qu'a-il donc pu se passer ? J'essaie d'attacher mon ancienne session.

open terminal failed: not a terminal

Evidemment. Un horrible pressentiment s'empare de moi...

uptime
21:14:32 up 1 min, 1 user, load average: 0.01, 0.01, 0.01

Mon monde s'écroule. Cette machine avait passé 1000 jours d'uptime. C'est déja un miracle qu'elle aie redémarré proprement. Elle tourne encore un kernel 2.6 openvz, un vieil openrc, un vieil udev...

su: must be run from a terminal

Voila autre chose. Impossible d'inspecter la situation sans un accès root. Je pars a la recherche d'une 3e machine, celle qui contient une clef ssh de secours, qui me permettra d'accéder directement au compte root.

La situation m'est familière; j'ai eu un ennui similaire sur mon eeePC, pendant une mise à jour d'openrc. Pour une raison bizarre, le script de boot responsable de monter le devpts sur /dev/pts se déclenche AVANT le montage d'un devtmpfs sur /dev, avec pour résultat un /dev/pts vide. En attendant, je remonte le /dev/pts à la main. Mon client SSH sur la tablette refonctionne, ouf.

Pour assainir le système, je procède enfin aux mises a jour que je procrastine depuis longtemps: udev (cauchemar), openrc, et le kernel. Dépendances et blocages se succèdent dans tous les sens.

jeudi 14 mai, 00h

Alors que mon nouveau kernel compile, je perds de nouveau la connexion. Petit instant d'angoisse; quelques minutes après, le serveur est de nouveau atteignable, mais la compilation a été interrompue. Je relance le processus, une fois, puis deux, puis trois, même problème. Quelque chose ne tourne pas rond.

uptime
00:02:14 up 1 min, 1 user, load average: 0.01, 0.01, 0.01

Saloperie. Qu'est-ce qui a bien pu se passer ? je fouille les logs. Rien de suspect. Puis, une intuition:

ipmitool sel list
10 | 05/14/2015 |  00:01:12 | Fan #0x54  | Upper Critical going high
10 | 05/13/2015 |  23:58:55 | Fan #0x54  | Upper Critical going high
10 | 05/13/2015 |  23:56:49 | Fan #0x54  | Upper Critical going high

D'accord. Un ventilateur mort, la machine surchauffe pendant les intensives compilations requises par les mises a jour.. Pas mal de choses commencent à s'expliquer.

Mon kernel est finalement compilé, mon udev est a jour. Je monte /boot, lance le make install, reconstruit mon initramfs avec genkernel, vérifie la configuration de grub, tout a l'air correct... Je me prépare a redémarrer. Mais un doute me taraude. Udev a été mis a jour, openrc également, j'ai un mauvais pressentiment. Et si l'interface réseau ne repart pas correctement ?

Cette machine n'a pas de KVM, on travaille sans filet. Si l'interface réseau ne repart pas, je suis bon pour attendre vendredi pour aller la dépanner physiquement. Pendant ce temps, tous les gens qui dépendent de cette machine (les amis d'IRC, et quelques associations) en pâtiront. Je décide de me préparer au pire.

Par chance, cette machine est cohébergée avec un deuxième serveur, lui-même parfaitement opérationnel. Un cable réseau croisé relie les deux systèmes, je décide de l'exploiter, et installe le script suivant dans /etc/rc.local/backdoor.start:

IFACE=`ip link |grep -B1 xx.xx.xx.xx.xx.xx |head -n1 |cut -d: -f2`
ip link set $IFACE up
ip addr add 10.10.10.10/24 dev $IFACE
nohup nc -l -p 1337 --continuous -e /bin/sh -s 10.10.10.10 &

Oui, c'est un risque sur le plan sécurité; mais l'interface est physiquement isolée du monde extérieur, personne n'est actuellement connecté sur l'autre machine, et nous n'utilisons pas ce subnet.

Je lance le reboot et croise les doigts.

jeudi 14 mai, 02h

Quelque chose n'a pas fonctionné. La machine ne répond ni sur son addresse publique, ni sur l'addresse interne habituelle. J'essaie le ping sur 10.10.10.10. ça répond.

J'ai été bien inspiré d'installer cette petite backdoor. Un nc plus tard, et je suis de nouveau aux commandes de la machine, encore une fois sans PTY, mais l'essentiel est la.

J'inspecte l'état de la machine. OpenSSH n'a pas démarré, et les deux bridges sont éteints. Sans cette backdoor improvisée, la machine était perdue. J'essaie de démarrer une des deux interfaces:

error: cannot create bridge

Je revérifie la configuration réseau, elle est correcte. Je met a jour bridge-utils. J'essaie de créer le bridge a la main, rien a faire... la commande échoue silencieusement. Mais enfin, que se passe-il ?

Soudain, l'inspiration me prend:

lsmod

Rien. Nada, zilch, zip, que d'alle. Pas un seul module chargé. Je réalise mon erreur avec horreur.

Je n'ai pas lancé le make modules_install du nouveau kernel.

Par chance, les drivers essentiels (disque et réseau) étaient en dur, tout comme le device-mapper. Un make modules_install plus loin, le module bridge se charge correctement; de tests en tests, tout a l'air de fonctionner. Je relance la machine, elle démarre complètement correctement... le plus gros incident est passé.

Il va maintenant falloir migrer tous les conteneurs d'openvz, qui n'est plus supporté...

mardi 14 octobre 2014

CTF Writeup: ASIS CTF 2014: Crypto 400 - Paillier

En donnée, on nous fournit l'addresse du service suivant:

max@truite ~ $ nc -v asis-ctf.ir 12445
DNS fwd/rev mismatch: asis-ctf.ir != mail.depository.ir
asis-ctf.ir [87.107.124.12] 12455 (?) open

        Here we use a well-known cryptosystem, which introduced in late 90s as a part of PhD 
        Thesis. This cryptosystem is a probabilistic asymmetric algorithm, so computer nerds 
        are familiar with the basics. The power of this cryptosystem is based on the fact that 
        no efficient general method for computing discrete logarithms on conventional computers 
        is known. In real world it could be used in a situation where there is a need for 
        anonymity and a mechanism to validate, like election.

    What's the name of this cryptosystem? 

Après quelques essais, on trouve Paillier:

    What's the name of this cryptosystem? 
Paillier 
The secret is: 9875676257636701658620619485901408458156381957610287297432150752657594971112130734695398259742040350122954870324237948599808827532539278700745263553319482092460456957407527479335203333233299470927024366020632206967357797846981812988215039671606873392079187791573839733015708764105651394898965004633566072121653336961074172004673994159863360102994472700677843818502473936852657203606418773655065969394463059460646887148864238467101809097431545413094791408119903360268021677565512905315679155054822925595572277268025072732035284201497048421809084512809302973116027126313140282915561007559382521979998979794092988861921 

Tell us your choise:
------------------------ 
[E]ncrypt: [D]ecrypt:  

Le nom du système est donc le bon. Nous avons une valeur secrète, un nombre en décimal, et apparemment la possibilité d'utiliser le service comme oracle, sans disposer directement de la clef.

Le service accepte de déchiffrer des valeurs abritraires, mais pas la fameuse valeur secrète:

Tell us your choise: 
------------------------ 
[E]ncrypt: [D]ecrypt: D  
Tell us your secret to decrypt: 98756 
Your original message is: 950874...........209298 
[E]ncrypt: [D]ecrypt: D
Tell us your secret to decrypt: 987567..........861921
Don't fool me! X-(

(J'ai raccourci les grands nombres par souci de lisibilité, mais le service donne les nombres complets)

La caractéristique distinctive du cryptosystème de Paillier réside dans ses propriétés homomorphiques. Si, par exemple, on à 3 messages clairs m, m1 et m2 tels que

m = m1 + m2 (mod n)

il est possible de calculer un texte chiffré c correspondant au message m, sans connaitre m1 et m2, en prenant

c = c1 c2 (mod n²)

Ici, notre objectif va donc être de retrouver le message m de notre secret, sans procéder à son déchiffrement. Pour ceci, nous allons d'abord trouver un c1 et un c2 acceptables, puis les déchiffrer, et il ne nous restera plus qu'a les additionner (mod n) pour retrouver le message original.

En supposant que le message m a été choisi arbitrairement, sans rechercher une valeur particulière de c, c est uniformément distribué dans le groupe multiplicatif M(n²), il est donc hautement probable qu'il contienne des petits facteurs. Essayons de trouver un petit facteur, avec haskell, par une technique tout à fait rudimentaire:

Prelude> let c = 98756762576...92988861921
Prelude> head [ k | k <- [2..], c `mod` k == 0 ]
11

On identifie presque immédiatement le petit facteur 11, et on calcule son cofacteur par division:

Prelude> c `div` c1
8977887.........362623811

On soumet alors les deux valeurs c1 et c2 à notre oracle: Tell us your choise: ------------------------ [E]ncrypt: [D]ecrypt: d Tell us your secret to decrypt: 11 Your original message is: 151709608361226950608367113680465803878157243458154889691251326923018155715697619180502339981181175975825978824071269220455262079491432880547349570206488156562505637347940621075801863098020222566004446665582027684319850545795810085447457566869848890807713892527339364953877439451805024781681882111584734863530 Tell us your choise: ------------------------ [E]ncrypt: [D]ecrypt: d Tell us your secret to decrypt: 89778875....23811 Your original message is: 6242769198942584817411105473450672386047972883716325422178669503309780681241088351102877529576142539995828596461517120317457326548163994292246457822325179469736425807552956065728181142742368861833271780719984831097410099764709060287670942937998909474785496814133308188930429303413286386679766196777006675616

On repasse ces messages dans Haskell:

Prelude> let m1 = 15170....863530
Prelude> let m2 = 62427....675616

Problème: nous savons maintenant que m = m1 + m2 (mod n), mais nous ne connaissons pas n. Comment le trouver ? En exploitant la propriété homorphique pour créer des valeurs équivalentes mod n, et en regardant leur hypothétique différence.

Par exemple, si on génère au hasard un texte chiffré ca, et qu'on soumet à l'oracle ca, puis ca², on obtiendra en retour deux valeurs ma et m2a telles que m2a = 2 ma (mod n); si on calcule x = m2a - 2 ma, x sera un multiple de n.

On peut faire le test avec quelques paires de valeurs simples: 2 et 4, 3 et 9, 5 et 25... coup de chance, le premier essai nous révèle immédiatement la valeur

157952377560169535425778219153916476264205216341871215113429996426327936396938707531605217510757318515821807420532786340772719406039596874839596028028813336032242063155493577141530044240762591427837718446302012515417260613072710825491978074491263004126928295563734080003249704892308810330085722662911791521557

Dont la taille est relativement proche du n recherché. On vérifie si cela est suffisant pour déchiffrer:

Prelude> let n = 157952...521557
Prelude> let m = (m1 + m2) `mod` n
Prelude> m
32487808320243150435316584796155571093777738593139558163862909500838275925645449950017589

Cette valeur est beaucoup plus petite que n, il est donc hautement probable qu'il s'agisse du bon message, sans padding. Mais comment l'interpréter ?

Prelude> import Numeric
Prelude Numeric> showHex m []
"415349535f3835633966656264346331353935306162316631396136626437613934663835"

Voila qui ressemble fortement à du décimal, affichons le en ascii:

Prelude Numeric> import qualified Data.ByteString as BS
Prelude Numeric BS> BS.reverse $ BS.unfoldr (\x -> if x == 0 then Nothing else Just (fromIntegral (x `mod` 256), x `div` 256)) m 
"ASIS_85c9febd4c15950ab1f19a6bd7a94f85"

samedi 11 octobre 2014

CTF Writeup: TinyCTF 2014: Crypto 200

CTF Writeup: TinyCTF 2014: Crypto 200

Analyse

Pour ce problème, on nous donne les deux fichiers suivants:

BJQOmVgJuDRqciWk748XXvMDHTP5dbU5jK4R4KzLkZXE41EnS7nbrB0bmBmuZ56NMARX8+X48xFQ
ZI+Dk8v1A+QLERQLiopR0ivFvHT9v9oOjavMZwTRKKop/kgFOIAb1N5CLm8aIh5HH3XYVaSQMyie
H1jg216NKi2rRzkSsbNe0FUokMi3MkYmbCftuQsVCaLV0gkjbiMFDEWs+BLfmLG+OovN/5iRx3Pa
oXty2z/VnNK2XuED7Hsk4TWOvhTMuGgxphffEGdN2EKTnd1FXnQdT8jxQhkXt4LRZgZRpTlpKKlG
Ybzfnw0vlW/GyiOEeO9EcB7vs7DlYQ3VVi/OZr4RsbXZ/8pjalIDfXzmzUTqgQuoTEnAKuKb0t4/
+gOujwWz5jPw8RxRNSjxQExmIXudVgXm8IacJb8CS5PONa7yqxbQ8U80yFDsHRPHPka9WGhpA79j
dAFCV5CV19KT+L01q/ZTcp7NDoSVSnOgfYUEygPTqkSmsI13bs+JScW3HVLiAA69ZhCj4Y9/c55J
WOBw7JuclJPJkNY3hQ0qrXUvtghZ9nanb8Hz4pVqvt0r2460n4isC5rgHTyEgYdTaAPHqZ5h6eTZ
4QrWCVLpOHtCQsJNBvP9skf0yLhUJbSajbanFhRKDmInPLcicJ+W+cJU6unV/JsaCrrjCvnaSa92
VXKQglHpm+rxYFpABDt86M+91JzbwzwCFtlmFlpfBFmds9zCQEE5JJvmyueLV5QpNFGmkCwYt3GX
WUdbMbl25AyNV5+EICgIg29d3wTUoe3yJVXHYS3xlz5Fs0MEXQK1qQp2DOu2nvhi/+LAI+4+5fOW
jAcSDpuNA2/ezK7Z8bfOZ49Ew+UHv1AVdRB4+ZDv4kj+94fzRXATRnkgfVmcqy1YUkJlFn068iCD
JaZx+aDO2UuQISHqpu6YLUwjtUP4Y1gCkaqxNP6oLJpxHRLSvBnvoWjAW+BwJYRCxG2pWrbx2/W+
+EX6SFJOvNox1eGcy2mDW9UIEu8BF/8z9DGQcvlDWctp65URM6+y1y4nc6VIDQSWk4kVPYMb5gB5
FcVx+IF9bVbtbtXf2l2FXk3asy7P2rwrXSI1cS0TImCTvaxsfCg0Fc3eVZtjjUKhnKl6hCwBv4i9
w+xV9x3M5bDa0lJwBGAa4rScXBoT7Pt+cXCTg4K3dyTCCK7Y18sfsjooWWweQ7ZNRjNsENrhgUb6
9NXrjELBZ0EJA9dvgP3eR5vv+1age7nO96VZV5tjfWJbeD50xJXElbFiqYNAwRzNw/1qEn8WN1f5
TL/8RUK5E+mTJY/9+F97BL5jcSbcGVp6aRDZQsyHAhShmKXphKRKksCCd4ZRUoC/c3m+ve/lecfl
qaaRFvYDkR0BAQ0cqTiCyP5Hkb9YCmBzFETrCfH1D8oN37nZkxCp7WmVUesXwWQz

et

-----BEGIN PUBLIC KEY-----
MIIEUzANBgkqhkiG9w0BAQEFAAOCBEAAMIIEOwKCBDIGLT1hySRSYwFH6JZw////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
//8CAwEAAQ==
-----END PUBLIC KEY-----

On remarque immédiatement la structure étrange de la clef. Affichons là avec openssl:

openssl rsa -pubin -noout -text <crypto200.pub
Public-Key: (8587 bit)
Modulus:
    06:2d:3d:61:c9:24:52:63:01:47:e8:96:70:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
...
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
    ff:ff:ff:ff:ff:ff:ff:ff:ff
Exponent: 65537 (0x10001)

La clef est très grande, mais remplie de bits 1. Le deuxième fichier, une fois décodé, fait 1074 bytes, soit 8592 bits; tout juste assez pour contenir un nombrebrut de la même taille de la clef.

Casser la clef

La clef publique exhibe une forme particulière. Pouvons nous l'exploiter ?

La clef fait 8587 bits, le préfixe du module (06:2d:3d:61:c9:24:52:63:01:47:e8:96:70) fait exactement 99 bits, il reste donc 8488 bits à 1, soit 1061 bytes.

Si on additionne 1 à cette valeur, on obtient le préfixe + 1, suivi d'une longe suite de zéros. On peut donc écrire:

n = 2^8488*x - 1

Ou x vaut 06:2d:3d:61:c9:24:52:63:01:47:e8:96:71.

Se pourrait-il que x soit un carré parfait ? si c'est le cas, on pose x = y^2, et on déduit immédiatement une factorisation de n en appliquant l'identité remarquable

(a-b)(a+b) = (a^2-b^2)

Qui nous donne

n = (2^4244*y - 1)(2^4244*y + 1).

x est de taille tout juste suffisante pour que y tienne dans un flottant à double précision. Essayons donc une racine carrée sur des flottants:

max@truite ~ $ ghci
Prelude> sqrt 0x062d3d61c92452630147e89671
6.99549860111847e14

Probablement suffisamment bon:

Prelude Numeric> let y = 699549860111847
Prelude Numeric> showHex y*y []
"62d3d61c92452630147e89671"

x est donc bien un carré parfait, et l'approximation du double n'a pas causé de problème, parfait. On obtient donc p et q:

Prelude Numeric> let p = 2^4244*y - 1
Prelude Numeric> let q = 2^4244*y + 1
Prelude Numeric> p
260687538913047604611581784183499992008451760653
...
6814857060351
Prelude Numeric> q
260687538913047604611581784183499992008451760653
...
6814857060353

Récupérer le flag

Puisque le message est au format brut, faisons les opérations nécessaires à la main avec haskell:

Prelude Numeric> let phi = (p-1)*(q-1)
Prelude Numeric> import EGCD
Prelude Numeric EGCD> let d = modInv 65537 phi
Just 619821027857093873....
....
385645407120058494507347279873

On charge le fichier et on décode la valeur en little-endian:

> import qualified Data.ByteString as B
> bytes <- B.readFile "ciphertext"
> let c = B.foldl' (\x y -> x*256 + fromIntegral y) 0 bytes

On calcule la version déchiffrée:

> let square x = x*x
> let modexp a e n = if e == 0 then 1 else if odd e then (a * modexp a (e-1) n) `mod` n else (square (modexp a (e `div` 2) n)) `mod` n
> let m = modexp c d n
> m
65151540921271072284844432466479370480767208216346753189456545359642913474452048348256443821114706423834256667231412670290529080763567179189546344566636337924315868233088893

Une valeur très petite par rapport à n, il est donc certain que ce déchiffrement est correct. Reste à l'interpréter correctement. On l'écrit simplement sous forme de bytes, little endian (c'est plus facile):

>  B.unfoldr (\x -> if x == 0 then Nothing else Just (fromIntegral (x `mod` 256), x `div` 256)) m
"}?n0_siht_nru7_uoy_0d_woh{galf :uoy rof taert a si ereH !snoitalutargnoC"

Bon, c'était du big endian:

> B.reverse $ B.unfoldr (\x -> if x == 0 then Nothing else Just (fromIntegral (x `mod` 256), x `div` 256)) m
"Congratulations! Here is a treat for you: flag{how_d0_you_7urn_this_0n?}"

mardi 29 juillet 2014

L'homme qui ne savait pas cuisiner

Il était une fois un homme, appelons-le monsieur B., qui ne savait pas cuisiner.

Aucune honte à cela, notez bien; chacun son métier, on ne peut pas tout savoir. Monsieur B était très doué dans son travail, mais n'avait aucun don aux fourneaux. Célibataire, il se nourrissait principalement de sandwiches et de plats précuisinés. C'est très pratique, les plats précuisinés: 3 minutes au micro-ondes, et on mange chaud.

Un jour, en discutant avec quelques amis aux tendances bobo/écolo/gauchistes, ceux-ci lui soutiennent qu'il existe une alternative infiniment supérieure à ses plats favoris: les produits frais.

Les produits frais n'ont que des avantages: ils sont moins chers (pour monsieur B., c'est important), et ils sont mieux tolérés par les estomacs fragiles des personnes agées. Le choix est beaucoup plus varié, on peut plus facilement personnaliser ses plats. Il paraîtrait même que dans les restaurants haut de gamme, on les utilise.

Monsieur B. connait le restaurant de l'entreprise, mais il n'a jamais été guigner dans les cuisines. Il s'imagine que la cuisine du restaurant ressemble probablement à la sienne, en plus grand; une rangée de fours micro-ondes, un grand frigo pour stocker les plats, un lave-vaisselle pour laver les plats, rien besoin de plus.

Néanmoins, il décide d'expérimenter ces fameux produits frais aux innombrables vertus. Il se rend donc au supermarché, et pour la première fois de sa vie, il explore d'autres rayons que celui des sandwiches et des plats micro-ondes.

Le choc est plutôt violent, il trouve des centaines de produits aux formes et couleurs étranges. Il achète un brocoli, rentre chez-lui, met son brocoli 3 minutes au micro-ondes. Il goûte, c'est dégueulasse.

Monsieur B. se dit qu'il n'a peut-être pas choisi le bon produit. Il observe un peu ce que les gens achètent, et choisit quelques produits au hasard: une pastèque, un camembert, une douzaine d'oeufs. Il les teste successivement,3 minutes au micro-ondes. C'est dégueulasse, son micro-ondes est couvert de bouillie de pastèque, d'oeuf explosé, et toute sa cuisine schmecte le camembert.

Monsieur B. est furieux d'avoir ruiné son micro-ondes et se plaint a ses amis. Ceux-ci l'écoutent d'abord, incrédules; puis, ne sachant trop par où commencer, lui suggèrent qu'il faut en fait, pour manger des produits frais, suivre une recette.

Monsieur B. se rend sur Gougle, et commence à chercher sur le Ouaibe des recettes de cuisine. Très vite, il s'énerve; la plupart des recettes contiennent du jargon incompréhensible, des expressions comme "brunoise de légumes", "déglacer au Grand Marnier" ou "épaissir au roux blond". Totalement incompréhensible pour un non-cuisinier.

Changeant d'approche, Monsieur B. s'inscrit sur un forum et poste une demande d'aide: "HELP, j'ai mis des oeufs au four, 3 minutes à 900W, tout à explosé, que faire ?". Le premier intervenant à lui répondre lui fait remarquer qu'il faut dire "four MICRO-ONDES" et pas "four", pour ne pas prêter à confusion. Monsieur B est un peu agacé par la pédanterie de ces cuisiniers, qui ergotent sur la terminologie au lieu de lui proposer des solutions.

Lassé, Monsieur B. décide qu'il lui sera plus simple, pour sa première dégustation de produits frais, de faire appel à un professionnel, et se rend au restaurant. Il commande un steak de boeuf aux champignons. Arrive l'addition, il s'étrangle: 48.- le steak de boeuf. Au supermarché, le steak coute 10.- et les champignons 2.- maximum. Comment ces cuisiniers osent-ils surfacturer à ce point leurs prestations ? 36 francs pour glisser une barquette dans un four, le régler sur 3 minutes et appuyer sur start ? inadmissible.

Monsieur B. retourne sur Internet, et tombe par hasard sur le forum d'une émission consacrée a la cuisine. Il y rédige une longue diatribe décriant les produits frais. Il y explique posément que les produits frais, c'est immangeable; il en a essayé une cinquantaine, à chaque fois c'était dégueulasse. On lui avait aussi dit que c'était moins cher, mais c'est un mensonge éhonté; au final, il faut payer un cuisinier très cher pour les préparer. C'est n'importe quoi, des produits qu'on ne peut pas préparer en les mettant 3 minutes au micro-ondes, ce qui est pourtant le standard universel de la cuisine. Vraiment, ça n'a aucun intérêt; ça ne peut que rester qu'un fantasme dans l'esprit de quelques cuisiniers.

Ami lecteur, si tu ne vois pas le rapport entre cette histoire et le logiciel libre, jette un oeil à cette rubrique et au premier commentaire posté dedans...

lundi 14 avril 2014

CTF Writeup: PlaidCTF 2014: RSA

Pour ce problème de forensics/crypto à 450 points, nous recevons en donnée les fichiers suivants:

Les données

"encrypted", en apparence aléatoire et inintelligible, d'exactement 128 bytes, soit 1024 bits:

00000000  9a 4b 89 34 b0 49 c8 0f  77 20 94 bf 1c 55 fe 9f  |.K.4.I..w ...U..|
00000010  d5 4f 55 2a 93 db 86 e3  2a 2b 32 d6 49 0f d2 6d  |.OU*....*+2.I..m|
00000020  8f 57 6d 8a 33 ec d4 bf  fd 20 25 e5 7f fb f1 5a  |.Wm.3.... %....Z|
00000030  4d ea 67 7a 29 3f 53 eb  b2 fd ba e1 c0 a5 5d f1  |M.gz)?S.......].|
00000040  02 4d 02 f9 a4 26 71 e5  5e e5 e4 49 e5 f7 8a 9e  |.M...&q.^..I....|
00000050  4f 37 db 2e 45 04 b0 fd  9d c9 13 9c 9c 76 4a e1  |O7..E........vJ.|
00000060  e3 6e fe a8 d9 81 3f 20  23 cb 0a 67 eb 78 c1 4d  |.n....? #..g.x.M|
00000070  95 75 7e 45 9b a4 66 cd  e6 36 14 e1 a8 2c 86 db  |.u~E..f..6...,..|
"public.pub", une clef publique au format openssl, de 1024 bits également:
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDb+r2xSV0ydudia4R5bp/CD6E8
F0TxDIw/PjwsYEDC5/MT36PR/hDRrld8/qt0UqpTEC7ve+AJnAIlYOV6XDDVCUBk
LRsJfdIQmuAvLc/4GYzVo5X8rEJmEHhIud1jw4fSU45QQVNDBCAz6gnAhBVeZSsP
BiNA1dRxekAqnYBqawIDAQAB
-----END PUBLIC KEY-----
Les détails de la clef:
max@truite ~/rsa $ openssl rsa -pubin -noout -text < public.pub 
Public-Key: (1024 bit)
Modulus:
    00:db:fa:bd:b1:49:5d:32:76:e7:62:6b:84:79:6e:
    9f:c2:0f:a1:3c:17:44:f1:0c:8c:3f:3e:3c:2c:60:
    40:c2:e7:f3:13:df:a3:d1:fe:10:d1:ae:57:7c:fe:
    ab:74:52:aa:53:10:2e:ef:7b:e0:09:9c:02:25:60:
    e5:7a:5c:30:d5:09:40:64:2d:1b:09:7d:d2:10:9a:
    e0:2f:2d:cf:f8:19:8c:d5:a3:95:fc:ac:42:66:10:
    78:48:b9:dd:63:c3:87:d2:53:8e:50:41:53:43:04:
    20:33:ea:09:c0:84:15:5e:65:2b:0f:06:23:40:d5:
    d4:71:7a:40:2a:9d:80:6a:6b
Exponent: 65537 (0x10001)
Et enfin, ce mystérieux fichier "corrupted.pem":
 r    e   y: (         
 o  lu :
      :d :f : d:b1:4 :5d: 2: 6:  : 2:  :8 :  :  :
      :c :0 : 1: c: 7:  :  :  :  : f:  :  :2c:6 :
      : 2:  : 3:  : f:  :d :  :  :  :a : 7:  : e:
     b:7 :  :  :5 : 0:2 :  :  : 0:  :9 :  :2 :  :
    e :7 :  :30:d :0 :  :  :  :  :  :  :  :  :  :
    e :  :  :  :  :  :  :  : 3:95:f : c:  :6 :  :
     8:  :b9:dd:  :  :  :  :5 :8e: 0:41: 3:  :  :
     0:3 :e :09: 0:  :1 :5 :6 :  :0 :0 : 3:  : 5:
     4:  :  :  :  :  :  :  : b
     c xpon n :   53  (0  0  1 
   v te xp   n :
     f:  :  : a: a:9 :e :  : 1: 2:  :  :e :  :1 :
    3 : 1:  :  :  : a:  :2 :  :  :  :  :  :  :  :
    9 : a:  :  :  :  :  : 5:c1: 0:b : 3: 2:0 :b0:
      :c : f:  :f :  :d2:  :  : d:  :1 :  :3 :  :
      :  :  :0 : 3:  :  : 5:c :  :3 :6 :  :a4:  :
    4 :  :  :8f:  :  :  :  : a:  : c:5f: 7: 6:  :
     1:  : b:  : 5:  :84:0 :b : f: 3:  :  : 4: 6:
      :  : 5:1 :  :d :  : f:  : c:  :  : 5:  :  :
      :e :f4:b :4 :8e:  :  
 r    :
    00:  :6 : 1:1 :  :b :0 : 2:c : b:2 :  : a:1 :
    c :  : 0:  :28:0 :  :cd:  : 8:  :  :20: c:  :
      : 5:  :9 : c:3 :  :  : a:b :c :3 :  :  :  :
     f:  :  : f: 1: 1:b :  : c:f : a:  :a :  :  :
     a:38:  :6 :  
  i   :
      :e :  :d :2 :6 : 7:  :33:  :46:  : 4:  :  :
      :5 :  : 4:6 :  : 6:  : e:d :  :  : 9: e:1 :
      :  :  :  :  :0 :  :  :  :c : 5:  :  :a :0 :
    6 :  :  :8 :e9:f : f:7 :5 : e:1 :  :  : 1:9 :
     4:d :e9: 6:  
 x  n   1:
     9:d : 5:  :c :67:  : 9:  :  :  : d:  :  : 3:
     f:6 : 0:c :  :6 :ad:  :2 :d :d :  :  :0 :7 :
      :5 : 6:  : 5:1 :f : d:  : 2:  :  : 2: 3:  :
    9 :  :  :  :  :67: 3:  :4 : 7:c0: 4:b :c :f :
      :3 :b : 1
 x on  t :
    1 : 9:47:8 :  :  :  : 3:  :  :  :6 :  :  :0 :
    e :e :8 :  :  :  :  : 1:c :74:  :  :d : 9:3 :
    5 : e:  : 2:  :7 : 2:c :  :  :  :  :5 :  : 8:
      :  :c :  : 1:  :a :  : 9: 5:  : 3:  : e:c :
      :  : 6:  
c e    i  t:
      :a :d :84:f :  : c:43:  :  :  : 6:  :  :  :
      : b:  :c :9 :  :  :  :  :  : 4:23:8b:  :6 :
    2 : 2:  :  : 7:5b:  :  :  :7 :  :  :  :  :  :
    f1:7 :1 :  :f : a:  : 5:  :  :  : 5:  : c: 1:
      :48: b: 6:  

Analyse

On reconnait le format texte d'openssl pour les clefs privées RSA. On peut comparer avec une clef privée générée pour l'occasion, pour connaitre les noms des différents champs:
max@truite ~/rsa $ openssl genrsa |openssl rsa -noout -text
Private-Key: (1024 bit)
modulus:
    00:ca:6d:bf:f1:cc:b4:8f:56:e7:c7:b3:29:7a:44:
...
Nous avons donc une clef privée dégradée, et selon toute vraisemblance, un fichier chiffré avec cette même clef
Heureusement, ce format de stockage est hautement redondant, pour des raisons de performance. En théorie, pour déchiffrer un message, seuls le module (n), déja présent dans la clef publique, et l'exposant de déchiffrement (d), sont nécessaires pour calculer un déchiffrement. Mais pour des raisons de performance, le format stocke aussi les deux nombres premiers ayant servi à la génération (p et q), les deux coefficients dp ≡ e-1 (mod p-1), et dq ≡ e-1 (mod q-1), et le coefficient c ≡ q-1 (mod p).
Ces valeurs supplémentaires servent à accélérer le calcul du déchiffrement, en appliquant le théorème des restes chinois. Cette optimisation existe uniquement pour le déchiffrement, pour deux raisons: d'abord, connaitre p et q permet le calcul de e à partir de d et vice-versa, ensuite parce que le choix d'un petit e rend déja le chiffrement suffisamment rapide (mais choisir un petit d est une très mauvaise idée puisqu'il devient possible de le retrouver par force brute)
Il faut noter que la connaissance de n'importe laquelle de ces valeurs permet de reconstruire les autres. Un algorithme pour reconstruire la clef est décrit dans un article de Nadia Heninger et Hovav Shacham, Reconstructing RSA Private Keys from Random Key Bits.

Une première attaque

Pour comprendre cet algorithme, réfléchissons à une première manière naive de reconstruire uniquement p et q à partir de leurs versions dégradées. On sait que n = p·q, nous avons donc n ≡ p·q (mod 2t). On peut donc essayer de reconstruire p et q bit par bit, en commençant par les lsb. Comme p et q sont premiers, ils ne sont pas divisibles par 2, donc leurs derniers bits respectifs sont 1. A chaque bit supplémentaire, nous devons considérer 4 possibilités (pour les 2 bits de p et q), mais 2 de ces possibilités sont éliminées par la contraite (n ≡ pq (mod 2t). Si un bit de p ou q est connu, on peut donc déduire le bit restant.
Malheureusement, si cette technique peut corriger quelques bits manquants, ici il y en a trop pour que l'attaque soit efficace; il nous faudra quand même tester par force brute un nombre considérable de combinaisons.

Une meilleure attaque

Nous allons exploiter les valeurs d, dpet dq pour aider la reconstruction. Je ne vais pas répéter ici les explications du papier, et sauter quelques optimisations mineures pour simplifier l'implémentation. Commençons par résumer les relations entre ces valeurs, en remplaçant les équivalences modulo par des coefficients explicites. Pour rappel, si a ≡ b (mod n), alors a = b + kn. Les équations, suivant la définition, sont:
  • e·d = 1 + k(p-1)(q-1) = 1 + k(n-p-q+1)
  • e·dp = 1 + kp(p-1)
  • e·dq = 1 + kq(q-1)
Ces équations restent valable après réduction modulo 2t, ce qui va nous permettre, la encore, de les reconstruire bit par bit. Mais il nous faut d'abord obtenir k, kp et kq.
Le code de l'attaque se trouve sur http://github.com/maugier/cctk dans PartialRSA.hs. Il utilise une lib maison, dans Partial.hs, pour la manipulation de chaînes de bits partiellement connues. Je ne reproduirai pas le code ici.
Pour reconstruire k, on va utiliser une approximation due à Boneh, Durfee et Frankel, qui nous indique d'une part que 1 < k < e, de l'autre que d' = ⌊(k·(n+1) + 1)/e⌋ est une bonne approximation de d, avec une marge d'erreur de (p+q), soit de l'ordre de la racine carrée de n, et donc la moitié des bits, si p et q sont a peu prs de la même taille.
On va donc simplement chercher la valeur de k par force brute. Le bon k sera celui pour lequel la moitié la plus significative des bits de d' correspond au d partiellement connu (il faut donc au moins log2(e) bits connus dans d pour avoir une solution unique à k.
breakK (n,e) d = [ k | k <- [1..(e-1)] 
                   , d >?< msb l . fromKnownInteger . approx $ k ] where
    approx k = (k * (n+1) + 1) `div` e
    l = (length (fromPartial d) `div` 2) + 2
Une fois k obtenu, nous pouvons calculer kp et kq. Je vous épargne le développement mathématique qui est dans le papier, nous allons simplement chercher les solutions de l'équation k'(k' - k(n-1) - 1) - k ≡ 0 (mod e). Les valeurs de kp et kq sont parmi les solutions pour k'. S'il n'y en a qu'une, kp = kq, s'il y en a deux il faut tester les deux permutations de la paire.
breakKPQ (n,e) k = [ k' | k' <- [1..(e-1)], (k'*(k' - c) - k) `mod` e == 0 ]
        where c = k*(n-1)+1

Maintenant que nous connaissons k, kp et kq, nous pouvons tenter de reconstruire les valeurs secretes, par une descente récursive dans l'arbre des solutions. Chaque étage i de cet arbre représente la connaissance des i bits les moins significatifs des 5 valeurs secrètes. Dans cet arbre, chaque noeud a potentiellement 25 enfants (1 bit supplémentaire inconnu pour chacun des 5 secrets), mais nous disposons de 4 équations, grâce auxquelles il ne reste que 2 enfants valide à chaque noeud. Attaquer les 5 valeurs simultanément est donc aussi cher (en complexité) qu'attaquer une seule des 5; mais en attaquant les 5 simultanément, nous pouvons éliminer les solutions intermédiaires incohérentes avec les fragments de valeurs connues. Avec suffisamment de bits connus, l'attaque se fait donc en temps linéaire sur la taille de la clef.
Comme solution de départ, toutes les valeurs secrètes sont impaires (p et q sont premiers; d, dp, dq sont tous inversibles modulo un nombre pair (respectivement (p-1)(q-1), (p-1) et (q-1)) et sont donc impairs.)
Nous pourrions faire tourner l'algorithme jusqu'a la récupération complète de dp ou dq, mais cela n'est pas nécessaire. Le plus simple est de récupérer p ou q, dont la taille est la moitié de n, et les autres valeurs suivront. (On pourrait aussi récupérer d, puisque la première phase du calcul du k nous révèle l'intégralité de la moitié supérieure des bits de d.) Notre fonction s'exécute dans la monade List, et backtracke automatiquement en cas de contradiction.

-- Une fonction qui étend une séquence partielle d'un bit, tout en fournissant sa valeur entière mod 2^i, et produit
-- les valeurs possible avec la valeur numérique correspondante
(>><) :: [Int] -> PartialBits -> [([Int],Integer)]
x >>< y = (extend (fromKnown x) >< y) >>= exhaustBit  

breakKey (n,e) s@[p,q,d,dp,dq] = do

    k <- breakK (n,e) d
    
    -- tester les deux permutations
    (kp, kq) <- case breakKPQ (n,e) k of
        [x]   -> [(x,x)]
        [x,y] -> [(x,y),(y,x)]

 
    -- tous les secrets sont impairs
    let slice0 = [[1],[1],[1],[1],[1]]

    -- extension d'un bit et pruning:
    let slice 0 = slice0
        slice i = do
           let m = 2^(i+1)
           -- on procède a l'extension de l'état précédent 
           -- légèrement sous-optimal mais plus concis
           -- (on pourrait étendre les variables séparément et déclarer
           -- les contraintes plus tôt.
           s' <- slice (i-1)  
           s'' <- zipWithM (>><) s' s

           -- les valeurs des chaines de bits
           let [pv,qv,dv,dpv,dqv] = map fromBits s''

           -- nos équations mod 2^i
           guard $ (pv * qv - n)                  `mod` m == 0
           guard $ (e * dv - (k*(n-pv-qv+1) + 1)) `mod` m == 0
           guard $ (e * dpv - (kp*(pv-1) + 1))    `mod` m == 0
           guard $ (e * dqv - (kq*(qv-1) + 1))    `mod` m == 0

           return s''

     -- on retourne q, le plus petit nombre premier
     [_,q,_,_,_] <- slice (length (fromPartial q))
     return q

On copie-colle ensuite les valeurs dégradées et on lance l'attaque:
n = fromHex "00:db:fa:bd:b1:49:5d:32:76...
e = 65537

d = fromPartialHex " f:  :  : a: a:9 :e :...
p = fromPartialHex "00:  :6 : 1:1 :  :b :...
q = fromPartialHex "  :e :  :d :2 :6 : 7:...
dp = fromPartialHex " 9:d : 5:  :c :67:  :...
dq = fromPartialHex "1 : 9:47:8 :  :  :  :...

main = print $ breakKey n e (p,q,d,dp,dq)
et on obtient la valeur de q: e945de2261e7b73317461ec48599715f2be4630866f99eda58a149ae102d1a91c4f909687f56ce65d7faab0f649d8e8ae9fc2f7e535e1d5aa76197b4d7e9a6cf.

Les finitions

Reste a transformer ce nombre en quelque chose d'utilisable. Puisque la clef était originellement au format OpenSSL, essayons de la recréer. Pour ça, j'utilise d'abord mes fonctions utilitaires en haskell pour recalculer p et d, puis j'utilise Crypto.PublicKey.RSA de pycryptopp:
max@truite ~/rsa $ python2
>>> from Crypto.PublicKey import RSA
>>> n = 15447482797676392...
>>> e = long(65537)
>>> p =  1264374063739511065289...
>>> q = 122174942057803188748651...
>>> d =  11066410079053154785483305869421...
>>> k = RSA.construct((n,e,d,p,q))
>>> print k.exportKey()
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQDb+r2xSV0ydudia4R5bp/CD6E8F0TxDIw/PjwsYEDC5/MT36PR
/hDRrld8/qt0UqpTEC7ve+AJnAIlYOV6XDDVCUBkLRsJfdIQmuAvLc/4GYzVo5X8
rEJmEHhIud1jw4fSU45QQVNDBCAz6gnAhBVeZSsPBiNA1dRxekAqnYBqawIDAQAB
AoGAD8JTypqd4ZqhEuzu7aAeM9HY1Cw6lSY3+ePkfa1bllr1kAvqeYXBALSDsgGw
mMG/T/oN0rxGHYoeoTzi07Q9DzP71RXFBT5p56SYTCa7j6THXXyqMLxfd+YFgVsr
ehXMhAi97yMeMoTmoQ91GN/cqW9n/MflJdm0aOv0skSOA0kCQQDxaVEeZr4GIsKr
LsFaF8DHoMcoCK7NuijH9SDsrSNlspzMNTHbGrzAPmk5aF/iFK/RQbqfbP06c6X6
6Fo482mlAkEA6UXeImHntzMXRh7EhZlxXyvkYwhm+Z7aWKFJrhAtGpHE+Qlof1bO
Zdf6qw9knY6K6fwvflNeHVqnYZe01+mmzwJAOdUVDcdnNmkVYZTt1Ptjv28QxtJt
rfMu2dgrbwd7N122mmUT8H1TQmqxIoOSlMKH7AVnA9JER8B0vsry8jm90QJAEllH
jsbKtjNTmlVjOesG6uiF73BCwVHIdP5C0Gk/Uv6yUrB1wsZuN76UXg446NfEf4Ex
rysZlQ+DaP7I387mKwJBAKXQhPcX/EP6kOMGR8eGc8sVy5tg55GQVpQjixZlIlLs
QrdbuK0Ad4szHWCm8XkRafba9EW966JFipzRfkg7Vjw=
-----END RSA PRIVATE KEY-----
On colle ça dans un fichier, rebuilt.pem, et on vérifie que la clef est bien celle que l'on attendait:
max@truite ~/rsa $ openssl rsa -noout -text < rebuilt.pem
Private-Key: (1024 bit)
modulus:
    00:db:fa:bd:b1:49:5d:32:76:e7:62:6b:84:79:6e:
    9f:c2:0f:a1:3c:17:44:f1:0c:8c:3f:3e:3c:2c:60:
    40:c2:e7:f3:13:df:a3:d1:fe:10:d1:ae:57:7c:fe:
    ab:74:52:aa:53:10:2e:ef:7b:e0:09:9c:02:25:60:
    e5:7a:5c:30:d5:09:40:64:2d:1b:09:7d:d2:10:9a:
    e0:2f:2d:cf:f8:19:8c:d5:a3:95:fc:ac:42:66:10:
    78:48:b9:dd:63:c3:87:d2:53:8e:50:41:53:43:04:
    20:33:ea:09:c0:84:15:5e:65:2b:0f:06:23:40:d5:
    d4:71:7a:40:2a:9d:80:6a:6b
publicExponent: 65537 (0x10001)
privateExponent:
    0f:c2:53:ca:9a:9d:e1:9a:a1:12:ec:ee:ed:a0:1e:
    33:d1:d8:d4:2c:3a:95:26:37:f9:e3:e4:7d:ad:5b:
    96:5a:f5:90:0b:ea:79:85:c1:00:b4:83:b2:01:b0:
    98:c1:bf:4f:fa:0d:d2:bc:46:1d:8a:1e:a1:3c:e2:
    d3:b4:3d:0f:33:fb:d5:15:c5:05:3e:69:e7:a4:98:
    4c:26:bb:8f:a4:c7:5d:7c:aa:30:bc:5f:77:e6:05:
    81:5b:2b:7a:15:cc:84:08:bd:ef:23:1e:32:84:e6:
    a1:0f:75:18:df:dc:a9:6f:67:fc:c7:e5:25:d9:b4:
    68:eb:f4:b2:44:8e:03:49
prime1:
    00:f1:69:51:1e:66:be:06:22:c2:ab:2e:c1:5a:17:
    c0:c7:a0:c7:28:08:ae:cd:ba:28:c7:f5:20:ec:ad:
    23:65:b2:9c:cc:35:31:db:1a:bc:c0:3e:69:39:68:
    5f:e2:14:af:d1:41:ba:9f:6c:fd:3a:73:a5:fa:e8:
    5a:38:f3:69:a5
prime2:
    00:e9:45:de:22:61:e7:b7:33:17:46:1e:c4:85:99:
    71:5f:2b:e4:63:08:66:f9:9e:da:58:a1:49:ae:10:
    2d:1a:91:c4:f9:09:68:7f:56:ce:65:d7:fa:ab:0f:
    64:9d:8e:8a:e9:fc:2f:7e:53:5e:1d:5a:a7:61:97:
    b4:d7:e9:a6:cf
exponent1:
    39:d5:15:0d:c7:67:36:69:15:61:94:ed:d4:fb:63:
    bf:6f:10:c6:d2:6d:ad:f3:2e:d9:d8:2b:6f:07:7b:
    37:5d:b6:9a:65:13:f0:7d:53:42:6a:b1:22:83:92:
    94:c2:87:ec:05:67:03:d2:44:47:c0:74:be:ca:f2:
    f2:39:bd:d1
exponent2:
    12:59:47:8e:c6:ca:b6:33:53:9a:55:63:39:eb:06:
    ea:e8:85:ef:70:42:c1:51:c8:74:fe:42:d0:69:3f:
    52:fe:b2:52:b0:75:c2:c6:6e:37:be:94:5e:0e:38:
    e8:d7:c4:7f:81:31:af:2b:19:95:0f:83:68:fe:c8:
    df:ce:e6:2b
coefficient:
    00:a5:d0:84:f7:17:fc:43:fa:90:e3:06:47:c7:86:
    73:cb:15:cb:9b:60:e7:91:90:56:94:23:8b:16:65:
    22:52:ec:42:b7:5b:b8:ad:00:77:8b:33:1d:60:a6:
    f1:79:11:69:f6:da:f4:45:bd:eb:a2:45:8a:9c:d1:
    7e:48:3b:56:3c
En effet, ça colle bien avec le fichier de départ. Puisque nous avons maintenant la clef au bon format, voyons si l'outil de déchiffrement d'openssl fonctionne:
max@truite ~/rsa $ openssl pkeyutl -decrypt -inkey rebuilt.pem < encrypted 
crypt0>>>f0rensics3~

SUCCESS !