The task contains ELF binary for ARM platform and the following Python script:```import requests
CHALLENGE_URL = "http://braincool.donjon-ctf.io:3200/apdu"
def get_public_key():    req = requests.post(CHALLENGE_URL, data=bytes.fromhex("e005000000"))    response = req.content    if response[-2:] != b"\x90\x00":        return None    return response[:-2]
public_key = get_public_key()assert public_key == bytes.fromhex("0494e92dd2a82e93d90c13322819db091a869c30c03c5a47d7b1f38683ba9bfdf33f44582dbd19e55e319ce5b2929fba6da9705c84df8c209441bcb713cf99c6d5d6e94445bc808e6821b73f3fa7d55b8a")```
ELF binary is not self-contained and uses syscalls like 0x60010B06 and same-privilege-level but external library with entrypoint at 0x120000; these are provided by Ledger Nano runtime (can be figured out in various ways - Magic OTP has a source-code example; "Ledger Nano" in UTF-16 is one of strings inside the binary; looking for products of the company that organizes the CTF; searching for syscall numbers, these are very specific). Entrypoint at 0x120000 dispatches many different functions by identifier defined in [https://github.com/LedgerHQ/nanos-secure-sdk/blob/1c16f9ad50f792c62a948aacb650258660f262cb/include/cx_stubs.h](https://github.com/LedgerHQ/nanos-secure-sdk/blob/1c16f9ad50f792c62a948aacb650258660f262cb/include/cx_stubs.h); the binary has corresponding wrappers with `push {r0,r1} // ldr r0,=<id> // b <helper label that branches to 0x120000>`. The repository also includes commented prototypes of all these functions.
One more thing besides SDK repository is very useful: [https://speculos.ledger.com/](https://speculos.ledger.com/) is an emulator for all this. System calls are handled by Python code, external library is provided as another binary in Speculos distribution. Speculos successfully loads binary from the task and serves a web page on http://localhost:5000 that (among other things) has an input named APDU, same as `CHALLENGE_URL` in the script above. Sending e005000000 results in something that doesn't exactly match bytes from the script but looks like the same structure. APDU is not invented by Ledger, there was a presentation [https://www.blackhat.com/presentations/bh-usa-08/Buetler/BH_US_08_Buetler_SmartCard_APDU_Analysis_V1_0_2.pdf](https://www.blackhat.com/presentations/bh-usa-08/Buetler/BH_US_08_Buetler_SmartCard_APDU_Analysis_V1_0_2.pdf) back in 2008 that describes the basics; APDUs have 5-byte header (CLA=class)(INS=instruction)(P1=param1)(P2=param2)(Lc=length) followed by Lc bytes of data; APDU from the script above has class 0xE0, instruction code 0x05, zero parameters and no data.
With this, reversing can finally start. Probably the easiest way to find the actual worker is to notice a string "CTF" in the binary and look for references to it. The worker is at 0xC0D00138 and accepts one argument that points to 5-byte header from APDU followed by 3 bytes of padding and a pointer to additional data, if any. The only recognized class is 0xE0 (whatever it means), there are 3 supported commands e005, e006, e007. e005 ignores parameters and data and returns something generated by the function at 0xC0D00374 (that is also called from e007 code path), which in turn calls the function at 0xC0D003A8 (that is also called from e006 code path) followed by `cx_ecfp_generate_pair2_no_throw(CX_CURVE_BrainPoolP320R1, (result), (output from 0xC0D003A8), 1, 0)`; so 0xC0D003A8 generates elliptic private key, 0xC0D00374 generates elliptic public key, and e005 command returns that public key.
Let's check bytes from the script with SageMath...```p = 0xD35E472036BC4FB7E13C785ED201E065F98FCFA6F6F40DEF4F92B9EC7893EC28FCD412B1F1B32E27q = 0xD35E472036BC4FB7E13C785ED201E065F98FCFA5B68F12A32D482EC7EE8658E98691555B44C59311E = EllipticCurve(GF(p), [0x3EE30B568FBAB0F883CCEBD46D3F3BB8A2A73513F5EB79DA66190EB085FFA9F492F375A97D860EB4, 0x520883949DFDBC42D3AD198640688A6FE13F41349554B49ACC31DCCD884539816F5EB4AC8FB1F1A6])G = E(0x43BD7E9AFB53D8B85289BCC48EE5BFE6F20137D10A087EB6E7871E2A10A599C710AF8D0D39E20611, 0x14FDD05545EC1CC8AB4093247F77275E0743FFED117182EAA9C77877AAAC6AC7D35245D1692E8EE1)Q = E(0x94e92dd2a82e93d90c13322819db091a869c30c03c5a47d7b1f38683ba9bfdf33f44582dbd19e55e, 0x319ce5b2929fba6da9705c84df8c209441bcb713cf99c6d5d6e94445bc808e6821b73f3fa7d55b8a)```...yep, no exception, this is a point on the curve.
e006 command requires 40 bytes of additional data, checks that first 3 bytes are not "CTF", generates private key, calculates some hashes in a loop and calls `cx_ecdsa_sign_no_throw`. e007 command requires at least 40 bytes of additional data, generates public key and calls `cx_ecdsa_verify_no_throw((public key), (pointer to additional data), 40, (pointer to additional data) + 40, (length) - 40)`; according to SDK, that means the data have to be 40-byte hash followed by a ECDSA signature of that hash. If `verify` succeeds, the code checks that first 3 bytes are "CTF", if so, outputs the result of more calculations involving some static byte arrays that look like decrypting of the flag.
There are (at least) two possible solutions for the task.
One solution is to ignore e006 command at all, focus on e007 command and recite how ECDSA verification works: given a hash `h` and a pair of modulo-curve-order integers `(r,s)`, calculate `u1=h/s`, `u2=r/s` modulo curve order, calculate a point `u1*G + u2*Q` and check whether x-coordinate equals `r` modulo curve order. We can start from random `u1` and `u2`, calculate `u1*G + u2*Q`, get `r` as x-coordinate, calculate `s` and `h` from `u1` and `u2` and get a valid triple (`h`,`s`,`r`) that passes the verification. We have no control over the resulting `h`, so this wouldn't work if `h` would be required to be an actual hash of something, but that is not the case for e007 function. We just need to forge a value with fixed 3 bytes; since `h` is essentially random, this requires 2^24 attempts on average with varying `u1` and `u2`.
Actually, the bottleneck is elliptic addition, so instead of random `u1`, `u2` I took `u2=1` and `u1=1,2,3,...` so that each attempt is just one elliptic addition:```u1 = 0u2 = 1R = Qwhile True:    u1 += 1    R += G    r = R[0].lift() % q    s = r    h = u1 * s % q    if hex(h).startswith('0x435446'):        print(r, s, h, u1, u2)        break```(okay, not strictly correct because 0x0435446 would also break the loop while being invalid for the problem, but whatever). My notebook found valid values in about ten minutesr=139311631778238424243685822929333226109973101219096009338726201981806436303919831322992698069905 s=139311631778238424243685822929333226109973101219096009338726201981806436303919831322992698069905 h=561774667424912276805954464527063183413505002816398854203852806056677912589630309235467827822607u1=19075642u2=1
It remains to serialize this to the expected format```def encode(a):    s = hex(a)[2:]    if len(s) % 2:        s = '0' + s    return '02' + '%02x' % (len(s) // 2) + sencoded = encode(r) + encode(s)encoded = '30' + '%02x' % (len(encoded) // 2) + encodedprint('e0070000' + '%02x' % (len(encoded) // 2 + 40) + hex(h)[2:].rjust(80,'0') + encoded)```and send the output `e00700007e435446f54766048a99fdbda8ae969fb988ba888100c4b60db858bd506d416a1d9cc33b7d420c400f``3054022810b2561d2a1fe9f79f0f3d38784733a86822495ad1d87b347ccd9dd3061c798577c44255c4be1391``022810b2561d2a1fe9f79f0f3d38784733a86822495ad1d87b347ccd9dd3061c798577c44255c4be1391` to the server.
Turns out this is not the expected solution. Another solution is to deeply dive into e006 command. It calls `cx_ecdsa_sign_no_throw((private key), 0x800, 4, (input additional data), (signature), &(signature length), 0)` and then outputs the content of `signature`. [Comments for the second argument](https://github.com/LedgerHQ/nanos-secure-sdk/blob/5e3e0595cf364cc784b247961879c707f495697b/include/lcx_ecdsa.h#L32) say that possible values are `CX_RND_TRNG` and `CX_RND_RFC6979`, that are [defined as 0x400 and 0x600](https://github.com/LedgerHQ/nanos-secure-sdk/blob/5e3e0595cf364cc784b247961879c707f495697b/include/lcx_common.h#L137) correspondingly; 0x800 is `CX_RND_PROVIDED` and has no comments except a single `#define`. Voyage inside nanos-cx-2.0.elf from Speculos distribution with a disassembler reveals that some value is somehow calculated depending on the mode, and 0x800 means to take that value from `signature` (that is otherwise output-only parameter). Given how ECDSA signing works, it is natural to assume that this value is nonce for signing, and it should be random. Really random. Further investigation of what happens to `signature` variable before the call shows that it is filled by hashing from bytes of the private key concatenated with the input hash; by itself, this is sufficiently close to random, but hash function is chosen as P1 from APDU, so it's output size can be less than supposed nonce size. In particular, P1=1 means 20-byte RIPEMD160 as opposed to 40-byte nonce. The code handles this by repeating the same calculation for the second half, making it identical to the first part, which is totally not random; nonce = (small value) * (2^160+1).
And if nonce is not random enough, the private key can be reconstructed. This case is not as severe as PS3 fiasco, but that just means we could need three valid signatures instead of two (it might work even with two signatures, or it might not work). One possible reference is [https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/](https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/). One of examples there is for small values of nonces and just needs additional (2^160+1) multiplier in the right place.* the first signature: request `e00601002800112233445566778899aabbccddeeff00112233445566778899aabbccddeeff0011223344556677` results in server's response `305402287b22f8718fe1a3094fd8795726add4b65bf8197d7c77e2d5c0c0f2514a8072e82dadd9bdcd821faf``0228605a9a0afc75c64f44cb50851b8a02dff8d7aa3fc0fef1326f419de67733b899a10ca46303e3a0829000`* the second signature: request `e0060100287766554433221100ffeeddccbbaa99887766554433221100ffeeddccbbaa99887766554433221100` results in server's response `30560229008e6327fc51da7fce1c036020c0c3b776bd11cb7d26e9a64d08b4ff8746c6b1c7082252f38dad73d6``02290084182f426dc70ea1354040afc3781131c80e02da2efecd46ee78c0345447930f4ca852c109f331da9000`* the third signature: request `e00601002800000000000000000000000000000000000000000000000000000000000000000000000000000000` results in `305502286c301ae0cf20599660b46ae813d5f0b92353a9e3c9bd42aba6471304010ae7e4b73fb46a0cb4de28``0229009bec1701a9eef8f6c4eedfccaccf5e0c75fbfdf63e062ef397cb7d7daba704eb0a6e1ed5fdd126fb9000`
With these, the final calculation in SageMath looks as follows:```h1 = 0x00112233445566778899aabbccddeeff00112233445566778899aabbccddeeff0011223344556677r1 = 0x7b22f8718fe1a3094fd8795726add4b65bf8197d7c77e2d5c0c0f2514a8072e82dadd9bdcd821fafs1 = 0x605a9a0afc75c64f44cb50851b8a02dff8d7aa3fc0fef1326f419de67733b899a10ca46303e3a082
u1 = s1.inverse_mod(q) * h1 % qu2 = s1.inverse_mod(q) * r1assert (u1 * G + u2 * Q)[0] == r1
h2 = 0x7766554433221100ffeeddccbbaa99887766554433221100ffeeddccbbaa99887766554433221100r2 = 0x8e6327fc51da7fce1c036020c0c3b776bd11cb7d26e9a64d08b4ff8746c6b1c7082252f38dad73d6s2 = 0x84182f426dc70ea1354040afc3781131c80e02da2efecd46ee78c0345447930f4ca852c109f331da
u1 = s2.inverse_mod(q) * h2 % qu2 = s2.inverse_mod(q) * r2assert (u1 * G + u2 * Q)[0] == r2
h3 = 0r3 = 0x6c301ae0cf20599660b46ae813d5f0b92353a9e3c9bd42aba6471304010ae7e4b73fb46a0cb4de28s3 = 0x9bec1701a9eef8f6c4eedfccaccf5e0c75fbfdf63e062ef397cb7d7daba704eb0a6e1ed5fdd126fb
u1 = s3.inverse_mod(q) * h3 % qu2 = s3.inverse_mod(q) * r3assert (u1 * G + u2 * Q)[0] == r3
s1inv = (s1*(2**160+1)).inverse_mod(q)s2inv = (s2*(2**160+1)).inverse_mod(q)s3inv = (s3*(2**160+1)).inverse_mod(q)m = matrix(QQ, [    [q, 0, 0, 0, 0],    [0, q, 0, 0, 0],    [0, 0, q, 0, 0],    [r1*s1inv, r2*s2inv, r3*s3inv, 2**160/q, 0],    [h1*s1inv, h2*s2inv, h3*s3inv, 0, 2**160]])
m.LLL()```The row with 2^160 in last column gives the solution in the form `(nonce1,nonce2,nonce3,privatekey*2**160/q,2**160)` that reveals the private key `m.LLL()[1,3]/(2**160/q)=-517794727213070440465809487079573886295422800895050539380236932863344970282509030853948351350774` (okay, the private key modulo curve order, but it does not make any difference). It remains to sign anything starting with `CTF` with the obtained key, send it to the server and receive the flag `CTF{8403b4f3a21a43a32d1e4a2ddd36571a51ec6aacb586fa7c71daebbeae62732d}`.