Cryptohack

Clearly the scheme given is not a hash function, in the sense that it is very easy to invert the function to obtain the original message. Hence, with any arbitrary hash, we can easily construct a message with that hash by inverting the operation. Python Implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 from pwn import * import json BLOCK_SIZE = 32 # Nothing up my sleeve numbers (ref: Dual_EC_DRBG P-256 coordinates) W = [0x6b17d1f2, 0xe12c4247, 0xf8bce6e5, 0x63a440f2, 0x77037d81, 0x2deb33a0, 0xf4a13945, 0xd898c296] X = [0x4fe342e2, 0xfe1a7f9b, 0x8ee7eb4a, 0x7c0f9e16, 0x2bce3357, 0x6b315ece, 0xcbb64068, 0x37bf51f5] Y = [0xc97445f4, 0x5cdef9f0, 0xd3e05e1e, 0x585fc297, 0x235b82b5, 0xbe8ff3ef, 0xca67c598, 0x52018192] Z = [0xb28ef557, 0xba31dfcb, 0xdd21ac46, 0xe2a91e3c, 0x304f44cb, 0x87058ada, 0x2cb81515, 0x1e610046] # Lets work with bytes instead!...

We will exploit the fact that numpy’s array class is int64. So, what we’re gonna do is basically generate random passwords, with digits, lowercase and uppercase letters and hope that one of these passwords have both sum and product (overflowed) prime. For this, we need password with three restrictions: It is large enough for the overflow to occur All the digits are odd (if we have any even digit, the product will be even, and therefore not prime) The length must be odd, so the sum will also be odd, as prime numbers should be odd numbers only I guess the last criteria is luck....

The vulnerability of the code (and yes, as somewhat hinted at by the challenge description), is these two lines: 1 2 nonce = sha1(long_to_bytes(privkey.secret_multiplier) + hsh).digest() sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce)) sha1 produces a digest of only 160 bits (20 bytes). This is a big problem as it is required that the nonce is a number randomly generated in the range between 1 and the order of the elliptic curve. In the above code, the hash generated by sha1 is only 160 bits long....

There is a bug in the implementation, specifically 1 2 3 4 5 6 def recover_x(self, xbit, y): xsqr = (y**2 - 1)*inverse(1 + self.d*y**2, self.p) % self.p x = pow(xsqr, (self.p + 1)//4, self.p) if x**2 == xsqr : ... return 0 the function recover_x will always return 0, as the check is not done on modulo $p$. The challenge is now straightforward as the base point has a x-coordinate of 0....

a and b is not given, but since we are given the two points, generator G and the public key point P, we can construct two equations in the form of $y ^ 2 = x ^ 3 + ax + b$. Solving the two linear congruent equation should give us $a, b$. Trying to do E = EllipticCurve(GF(p), [a, b]) lead to an error by Sage that the curve defined is not a elliptic curve, rather a singular curve....

Simple challenge, there are two key point to solve this. First, the order of the curve is smooth, and also the private keys are relatively small ($2 ^ {64}$). My approach is just simply relying on Sage magic to perform the heavy duty work. Sage Implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 from Crypto....

It is ECDSA, except that there is no hashing algorithm in use. Instead, the hashing algorithm just returns the data that it passes in. This makes it trivial to forge messages with the correct signatures. 1 2 3 4 5 6 7 class HashFunc: def __init__(self, data): self.data = data def digest(self): # return hashlib.sha256(data).digest() return self.data The following is referring to this question on Crypto StackExchange. The answer mentions how the signing of a message is carried out....

A classic example in timing/power analysis of multiplication algorithms. This boils down to how the double-and-add algorithm is implemented, and bears great resemblance to the square-and-multiply method. The following is the pseudocode for the algorithm of computing $sP$, where $P$ is the given point and $s$ is the number we want to multiply. 1 2 3 4 5 6 7 8 let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s let res = O # point at infinity let temp = P # track doubled P value for bit in bits: if bit == 1: res = res + temp # point add temp = temp + temp return res We can clearly see that if the if branch is taken, an additional addition step is taken....

An elliptic curve $E$ defined over $F_p$ whose cardinality (or order) is also $p$ is an anomalous curve, and the discrete logarithm becomes trivial. We can employ Smart’s attack, which allows us to perform the discrete log of the curve in linear time. This paper by Novotney goes over the details of why the attack works. At the time of writing, I wish I understand what’s in the paper - some very topics into group theory....

We can factor $N$ using the given phi, or just simply look up the number on FactorDB. If the number returned has the form of $c = g ^ {k}$ with some even number $k$, we have the observation that for every factor of $N$, $c$ is a quadratic residue under that base, whereas the randomly generated number almost never generate a number that is a quadratic residue of all factors....