Log in as admin to get the flag.
nc pki.hackable.software 1337
This was a fun challenge, because it required many steps to complete. The first thing we notice is that MD5 is being used:
def h(x):
return int(hashlib.md5(x).hexdigest(), 16)
def makeMsg(name, n):
return 'MSG = {n: ' + n + ', name: ' + name + '}'
def makeK(name, n):
return 'K = {n: ' + n + ', name: ' + name + ', secret: ' + SECRET + '}'
def sign(name, n):
k = h(makeK(name, n))
r = pow(G, k, P) % Q
s = (modinv(k, Q) * (h(makeMsg(name, n)) + PRIVATE * r)) % Q
return (r*Q + s)
Naturally, we cannot register as 
from coll import Collider, md5pad, filter_disallow_binstrings
import os
def nullpad(payload):
return payload + b'\x00' * (64 - len(payload) % 64)
def left_randpad(payload):
random_string = os.urandom(64)
return random_string[:len(payload) % 64] + payload
# nullpad the prefix so that it does not interfere
# with the two collision blocks
prefix = nullpad(b'K = {n: ')
suffix = b', name: groci, secret:'
collider = Collider()
collider.bincat(prefix)
collider.safe_diverge()
c1, c2 = collider.get_last_coll()
collider.bincat(suffix)
cols = collider.get_collisions()
# here are our collisions!
A = next(cols)
B = next(cols)
The above code creates a collision such that k = h(makeK(name, n)) generates the same value. The problem is that the server does not return the signature, but str(pow(sign(name, n), 65537, int(n.encode('hex'), 16))).
To get the signature, which is computed as 
The probability that it is smooth enough is not very high. Also, the number is around 
Well… what if 
import hashlib
from Crypto.Util.number import isPrime
def num2b(i):
c = hex(i).strip('L')
c = (len(c) % 2) * '0' + c[2:]
return c.decode('hex')
# get the payloads
A = int(A[64:64*3].encode('hex'), 16)
B = int(B[64:64*3].encode('hex'), 16)
# PURE BRUTEFORCE, NOTHING FANCY HERE!
# append the same data to both payload until
# they resulting numbers are BOTH prime
mul = 2 ** 96
for i in range(1, 2**20, 2):
if isPrime(AA + i) and isPrime(BB + i):
print AA+i
print BB+i
break
As an example, we obtain
and
Putting this into action, we might do something like:
def connect(name, n):
name_encoded = base64.b64encode(name)
n_encoded = base64.b64encode(n)
server = remote('pki.hackable.software', 1337)
payload = 'register:' + name_encoded + ',' + n_encoded
server.send(payload + '\n')
return pow(int(server.recvline()), modinv(65537, n1-1), n1)
payload1 = nullpad('K = {n: ') + num2b(n1)
payload2 = nullpad('K = {n: ') + num2b(n2)
name = 'groci'
PORT = 1331
assert(h(makeK(name, payload1)) == h(makeK(name, payload2)))
assert(h(makeMsg(name, payload1)) != h(makeMsg(name, payload2)))
# Get first signature
sig = connect(name, payload1)
r1, s1 = sig / Q, sig % Q
z1 = h(makeMsg(name, payload1))
# Get second signature
connect(name, payload2)
sig = pow(int(server.recvline()), modinv(65537, n2-1), n2)
r2, s2 = sig / Q, sig % Q
z2 = h(makeMsg(name, payload2))
# Make sure we got a nonce re-use
assert(r1 == r2)
# OK, use standard nonce re-use technique...
delta = modinv(((s1 - s2) % Q), Q)
k = ( ((z1 - z2) % Q) * delta) % Q
r_inv = modinv(r1, Q)
PRIVATE = (((((s1 * k) % Q) - z1) % Q) * r_inv) % Q
# Now that we know the private key,
# lets forge/sign the admin account!
name = 'admin'
n = 'snelhest'
k = h(makeK(name, n))
r = pow(G, k, P) % Q
s = (modinv(k, Q) * (h(makeMsg(name, n)) + PRIVATE * r)) % Q
sig = r*Q + s
# connect and login
name_encoded = base64.b64encode(name)
n_encoded = base64.b64encode(n)
server = remote('pki.hackable.software', 1337)
payload = 'login:' + name_encoded + ',' + n_encoded + ',' + base64.b64encode(num2b(sig))
server.send(payload + '\n')
print server.recvline()
We obtain the following signatures:
Now, with our forced nonce re-use, we can use standard techniques to obtain the private key and sign our
DrgnS{ThisFlagIsNotInterestingJustPasteItIntoTheScoreboard}!
Note to reader: I apologize for the excessive use of memes.
, i.e. 
. Then, the secret becomes 
. Notably, the first block 
contains the hash, but encrypted.
as username? Then, we have encrypted 
, but we want only 
. As mentioned before, the hash fits perfectly into a single block. So, by removing the 
, 
, which is all what we need.![\mathbb F_2[x]/P(x)](https://s0.wp.com/latex.php?latex=%5Cmathbb+F_2%5Bx%5D%2FP%28x%29&bg=ffffff&fg=000000&s=0&c=20201002)
with the mapping that, for instance, an integer 
is 
in binary, which corresponds to a polynomial 
. The code is doing 
in 
.
to be the key and 
the seed. Note that all elements are in 
is unknown.
and 
. The individual square roots exist and are unique.
with the exception that elements are in 
this time. We omitt the multiplication symbol from now on.
matrices (with elements in 
and 
.
to a power yields has a closed form formula: 
.
, we call this 
via a square-and-multiply type algorithm. In python, it would be
be the random value fed to the function. Once 
is computed, it returns
. Adding this to the above yields
.
. Note that given two elements of the key stream, all these elements are known. Once determined, we compute the (dicrete) 
to find 
.
fixed to obtain the flag 
. Let us reorder the function as follows:
, since we can control 
. Equivalently, we can encrypt for different values of 
, where the trailing six bits will be the trailing six bits of 
.
time and space. This is done by putting about 
values of the encryption (or decryption) in a table. Then, we generate the decryptions (or encryptions, respectively) and look in the table.
. 
, 
. (This is not true, thanks to hellman for pointing that out in the comments).
. Having a look at the Wikipedia page, I found that this is how AES-CFB/(CBC) would behave (image from Wikipedia):
, we can inject some data into the decrypted ciphertext! Assume that we want 
. Then, we can set 
, since then 
. Embodying the above in Python, we might get something like
while ensuring a low level of detection in the presence of a warden Willie, who observes the communication through another discrete memoryless channel with crossover probability 
. We assume that all parts are equally computationally bounded.
for non-zero 
. Let 
be a sequence of secret bits she wants to transmit.
bits are shared between Alice and Bob, they can transmit 
secret bits without Willie seeing them (with high probability).
.
.
over the channel.
(LPN) and can be solved with the BKW algorithm (or similar) if 
are zero and does not contribute. For some probabilities 
and natural number 
, so
.
and 
using a simple Gaussian elimination step, i.e., writing the equations as
.
, but what about when the equations share unknowns but are defined under different moduli? Let us take a real-world scenario from the realm of cryptography.
and 
. To sign a message (invoking 
be a hash function and 
the message to be signed:
.
. If 
, go to step 2.
. If 
, go to step 2.
.
or 
is not satisfied, reject the signature.
.
.
.
.
, accept. Otherwise, reject.
for some public parameters 
. Assuming that 
, we obtain equations
. In solving actual multivariate equations, we will hit a brick wall, as needed operations such as row reduction and modular inversion does not work.
and an integer 
, there exists two integers 
such that
.
and 
are two basis vectors that spans the space below. They are not unique in that sense, but evidently, they are the shortest basis vectors possible (such a basis can be found using the LLL algorithm). If the two column vectors 
. Here, 
.
. Sloppily formulated: for a given lattice 
. In this scenario, we are given a vector 
in the vector space (but it might not be in 
. There is also a reduction in the other direction, which involves extending the basis of 
to be close in the normed space. By adding additional constraints we may perform the following minimization:
, 
and 
. Finding a closest approximation (preferably, using LLL/Babai) yields a solution to the DSA equations using LCG.
and 
, find the sequence 
such that
. This is called the Merkle-Hellman public-key cryptosystem. It is easy to see that encryption actually is the encoding procedure mentioned above. However, the decryption procedure is a bit more involved; in fact it requires a special class of instances. If the weights can be transformed into a super-increasing sequence, the problem becomes trivial to retrieve the sequence 
weight. Then, if the target sum 
(if not, 
. We can now remove 
and 
. This procedure can be repeated until all weights have been found (or 
).
in the following way
. Depending on the instance, this may or may not be the case. So, how do we penalize the algorithm for choosing values outside the allow set?
in the following manner:
on the number of non-zero values in the solution.
.
is false solution and a reduced-basis vector of 
. If 
, this is 
, which is a noticeable reduction for most values of 
. Since the sieve requires time 
, we do not need to do better than that. But can we match it? Turns out we can.
is the divisor counting function which has the properties 
(and, thus, 
) and 
.
. That is 
. We split the range into even numbers and for even 
compute
.
, compute 
, and so forth up to 
. The requires 
operations.
operations. Now, we have 
. So the complexity is 
. This is a harmonic series and treating it as an integral, we have 
. Of course, we do only generate primes up to 
. So we are done 🙂
, which is 
and uses basically no memory. This can be written as
, which is exactly 
. This contributes with 
. Doing it for all possible divisors, we end up with the sum of sum of divisors.
. Here is how:
and in the right table 
where 
:
. Then 
.
be the sum of all divisors of 
. For example, 
and 
. Find 
.
values in memory, we will run into a wall very fast (this is about 
TBs assuming that each number is a 64-bit integer – note the modular reduction which can be done in every step). Clearly, we need to use the memoryless approach.
only holds when 
. Then 
. The case of 
, we will have
? We can estimate the how many numbers in the product for which it that holds 
. Take, 
. We have 
, so
. Let us consider the case 
. The (negative) contribution from this set![p \cdot \underbrace{\left[ \left(\sum_{i=2}^Ni\left\lfloor \frac{N}{i \cdot p} \right\rfloor\right)^2 - C({N}/{p})\right]}_{=S(N/p)}](https://s0.wp.com/latex.php?latex=p+%5Ccdot+%C2%A0%5Cunderbrace%7B%5Cleft%5B+%5Cleft%28%5Csum_%7Bi%3D2%7D%5ENi%5Cleft%5Clfloor+%5Cfrac%7BN%7D%7Bi+%5Ccdot+p%7D+%5Cright%5Crfloor%5Cright%29%5E2+-+C%28%7BN%7D%2F%7Bp%7D%29%5Cright%5D%7D_%7B%3DS%28N%2Fp%29%7D&bg=ffffff&fg=000000&s=0&c=20201002)
.
), we get
, it takes too long (as we are aiming for the sub-minute mark):
is the Möbius function, defined
time. The Möbius function can be pre-computed in 
, we need both dice to have the identity 
(otherwise, we will not be able to reach 
). So, 
.
. It must be on both dice, or we would have 
. So, 
. Also, since 
and their powers (e.g 
) that does not exist on the original dice, because then impossible products could be reached.
must be on both dice, giving 
. There are 
. Now, there is no space left for 
on the smaller die. This means that 
must be one the larger die, but then 
, which is a contradiction.
.
.
.
and 
, respectively.
be i.i.d random variables taking values in the range ![[1,4]](https://s0.wp.com/latex.php?latex=%5B1%2C4%5D&bg=ffffff&fg=000000&s=0&c=20201002)
and let 
taking values in the range ![[1,6]](https://s0.wp.com/latex.php?latex=%5B1%2C6%5D&bg=ffffff&fg=000000&s=0&c=20201002)
. We want to determine the probability that 
.
, we may express it as
.
ways in which five six-sided dice (sides numbered 
to 
. Some examples are:
) be rolled so that the top ten sum to 
?
. If we restrict the remaining ten dice to be less than or equal to the minimum value of the ten dice, we then can compute the cardinality. Let 
denote the number of 
where 
.![[1, j]](https://s0.wp.com/latex.php?latex=%5B1%2C+j%5D&bg=ffffff&fg=000000&s=0&c=20201002)
, where 
is the left-most non-zero index (starting from 
, where 
.
. Disregarding 
, we compute all permutations of a given histogram in the same way (hence, we can make the search space a lot smaller) and the using the multiplicity to determine the exact number. All and all, the following code gives our answer: