BSides’17 – Delphi

In this challenge, we are given a server which accepts encrypted commands and returns the resulting output. First we define our oracle go(cmd).

import urllib2

def go(cmd):
	return urllib2.urlopen('' + cmd).read()

This simply return the status from the server. It is common for this kind of CTF challenges to use some block-cipher variant such as some of the AES modes.

The first guess I had was that AES-CBC was being used. That would mean that if we try to flip some bit in a block somewhere in the middle of the ciphertext, the first decrypted part would remain intact, whilst the trailing blocks would get scrambled.

Assume that we have four ciphertext blocks C_0, C_1, C_2, C_3 and the decryption is \textsf{dec}_k : C_0\| C_1\| C_2\| C_3 \mapsto P_0\|P_1\|P_2\|P_3. Now, we flip a bit in C_1 so that we get C_1', then we have \textsf{dec}_k : C_0\| C'_1\| C_2\| C_3 \mapsto P_0\|P'_1\|P'_2\|P'_3. (This is not true, thanks to hellman for pointing that out in the comments).

Turns out this is not the case. In fact, the error did only propagate one block and not further, i.e.,\textsf{dec}_k : C_0\| C'_1\| C_2\| C_3 \mapsto P_0\|P'_1\|P'_2\|P_3. Having a look at the Wikipedia page, I found that this is how AES-CFB/(CBC) would behave (image from Wikipedia):



Since \textsf{dec}_k(C_0) \oplus C_1 = P_1, we can inject some data into the decrypted ciphertext! Assume that we want P'_1 = Q. Then, we can set C'_1 = C_1 \oplus P_1 \oplus Q, since then \textsf{dec}_k(C_0) \oplus C'_1 = P_1\oplus P_1 \oplus Q = Q. Embodying the above in Python, we might get something like

def xor(a, b):
    return ''.join(chr(ord(x) ^ ord(y))
              for x, y in zip(a, b))

cmd = '8d40ab447609a876f9226ba5983275d1ad1b46575784725dc65216d1739776fdf8ac97a8d0de4b7dd17ee4a33f85e71d5065a02296783e6644d44208237de9175abed53a8d4dc4b5377ffa268ea1e9af5f1eca7bb9bfd93c799184c3e0546b3ad5e900e5045b729de2301d66c3c69327'
response = ' to test multiple-block patterns' # the block we attack

split_blocks = [cmd[i * 32: i * 32 + 32]
                for i in range(len(cmd) / 32)]

block = 3 # this is somewhat arbitrary

# get command and pad it with blank space
append_cmd = '  some command'
append_cmd = append_cmd + '\x20' * (16 - len(append_cmd))

new_block = xor(split_blocks[block].decode("hex"),
new_block = xor(new_block.decode("hex"),

split_blocks[block] = new_block
cmd = ''.join(split_blocks)
#print cmd
print go(cmd)

We can verify that this works. Running the server, we get

This is a longer string th\x8a\r\xe4\xd9.\n\xde\x86\xb6\xbd*\xde\xf8X\x15I  some command  e-block patterns\n

OK, so the server accepts it. Nice. Can we exploit this? Obviously — yes. We can guess that the server does something like

echo "{input string}";

First, we break off the echo statement. Then we try to cat the flag and comment out the rest. We can do this in one block! Here is how:

append_cmd = '\"; cat f* #'

Then, the server code becomes

echo "{partial + garbage}"; cat f* #{more string}";

The server gives the following response:

This is a longer string th:\xd7\xb1\xe8\xc2Q\xd7\xe8*\x02\xe8\xe8\x9c\xa6\xf71\n

Indeed, this is the flag. So, we are done!


We are given the following implementation of a HMAC where the hash function has been replaced by a CRC function.

CRC_POLY = to_bits(65, (2**64) + 0xeff67c77d13835f7)
CONST = to_bits(64, 0xabaddeadbeef1dea)

def crc(mesg):
  mesg += CONST
  shift = 0
  while shift < len(mesg) - 64:
    if mesg[shift]:
      for i in range(65):
        mesg[shift + i] ^= CRC_POLY[i]
    shift += 1
  return mesg[-64:]

INNER = to_bits(8, 0x36) * 8
OUTER = to_bits(8, 0x5c) * 8

def xor(x, y):
  return [g ^ h for (g, h) in zip(x, y)]

def hmac(h, key, mesg):
  return h(xor(key, OUTER) + h(xor(key, INNER) + mesg))

We are given two messages PLAIN_1 = "zupe zecret"; PLAIN_2 = "BKPCTF", of which HMAC_1 = hmac(crc, key, bin(PLAIN_1)), where bin() is a binary vectorial representation.
First, we note that the CRC operation is actually interpretable as a simple modular polynomial expression. Also, every binary sequence can be written as a polynomial \mathbb{F}_2[x] / P(x). We use the following mapping: H(x)HMAC_1; M(x)mesg; C(x), CONSTO(x) , OUTER; I(x) , INNER; P(x)CRC_POLY and K(x)key).

[M(x)x^{64} + C(X)] \mod P(x).

Consequently, the HMAC operation can be written as

H(x) = ([K(x)+O(x)]x^{64} + [K(x)+I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x) \mod P(x).

Secondly, we note that can move out the K(x) from the expression, i.e.,

H(x) = \underbrace{([O(x)]x^{64} + [I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x)}_{\textnormal{Independent of the key}} + K(x)(x^{128}+x^{128+n}) \mod P(x).

With some simple algebra, we can now determine the key K(x) by rearranging the above equation

\left(H(X) + ([O(x)]x^{64} + [I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x)\right)(x^{128}+x^{128+n})^{-1} = K(x) \mod P(x).

Using Sage, the we can easily do these computations:

def bits_to_hex(b):
  return hex(from_bits(b)).rstrip("L")

def from_bits(N):
  return int("".join(str(i) for i in N), 2)

P.<x> = PolynomialRing(GF(2))
I = P.ideal([x^64+x^63+x^62+x^61+x^59+x^58+x^57+x^56+x^55+x^54+x^53+x^52+x^50+x^49+x^46+x^45+x^44+x^43+x^42+x^38+x^37+x^36+x^34+x^33+x^32+x^31+x^30+x^28+x^24+x^21+x^20+x^19+x^13+x^12+x^10+x^8+x^7+x^6+x^5+x^4+x^2+x^1+1])
S = P.quotient_ring(I)
In =  x^61+x^60+x^58+x^57+x^53+x^52+x^50+x^49+x^45+x^44+x^42+x^41+x^37+x^36+x^34+x^33+x^29+x^28+x^26+x^25+x^21+x^20+x^18+x^17+x^13+x^12+x^10+x^9+x^5+x^4+x^2+x^1
Out =  x^62+x^60+x^59+x^58+x^54+x^52+x^51+x^50+x^46+x^44+x^43+x^42+x^38+x^36+x^35+x^34+x^30+x^28+x^27+x^26+x^22+x^20+x^19+x^18+x^14+x^12+x^11+x^10+x^6+x^4+x^3+x^2
M =  x^86+x^85+x^84+x^83+x^81+x^78+x^77+x^76+x^74+x^72+x^70+x^69+x^68+x^62+x^61+x^58+x^56+x^53+x^46+x^45+x^44+x^43+x^41+x^38+x^37+x^34+x^32+x^30+x^29+x^25+x^24+x^22+x^21+x^20+x^17+x^14+x^13+x^10+x^8+x^6+x^5+x^4+x^2
Hmac =  x^63+x^61+x^58+x^56+x^54+x^53+x^52+x^51+x^50+x^48+x^46+x^41+x^40+x^39+x^37+x^29+x^28+x^25+x^23+x^22+x^21+x^20+x^19+x^18+x^17+x^15+x^13+x^12+x^9+x^7+x^2+x^1
CONST = x^63+x^61+x^59+x^57+x^56+x^55+x^53+x^51+x^50+x^48+x^47+x^46+x^44+x^43+x^42+x^41+x^39+x^37+x^35+x^34+x^32+x^31+x^29+x^28+x^27+x^26+x^25+x^23+x^22+x^21+x^19+x^18+x^17+x^16+x^12+x^11+x^10+x^8+x^7+x^6+x^5+x^3+x^1
Y = Hmac + ((Out)*x^64 + ((In)*x^88 + M)*x^64 + CONST)*x^64 + CONST
X = (x^128+x^(128+88))
Xinv = X.xgcd(x^64+x^63+x^62+x^61+x^59+x^58+x^57+x^56+x^55+x^54+x^53+x^52+x^50+x^49+x^46+x^45+x^44+x^43+x^42+x^38+x^37+x^36+x^34+x^33+x^32+x^31+x^30+x^28+x^24+x^21+x^20+x^19+x^13+x^12+x^10+x^8+x^7+x^6+x^5+x^4+x^2+x^1+1)[1]
K = S(Xinv*Y)
Kbin = [K[i] for i in range(0,64)]
print "The key is", bits_to_hex(Kbin)

and obtain the key 0xae5617703acedc88. Substituting the key into the code, we get the flag BKPCTF{0xd2db2b8b9002841f}.

PlaidCTF 2015 : Strength

This challenge was one of the crypto related tasks during PlaidCTF 2015. The attacker (you) is given a set of public keys and corresponding ciphertexts of the same message. The task is to recover the plaintext (flag).

\left\{ \begin{array}{ccc} c_1 & = & m^{e_1} \bmod{N} \\ c_2 & = & m^{e_2} \bmod{N} \\ & \vdots & \\ c_k & = & m^{e_k} \bmod{N}\end{array} \right.

A fairly trivial observation is as follows: if we succeed to find a linear combination such that \sum_{i=1}^k a_ie_i = 1, a_i \in \mathbb{Z}, then it can be used to unravel the message, i.e.,

\prod_{i=1}^k(m^e_i)^{a_i} = m^{\sum_{i=1}^k a_ie_i} = m

In fact, it suffices to find two relatively prime e_i and e_j. Given these exponents, we can use the Euclidian algorithm without modification to find a linear combination that is \pm 1. Scanning through the list, we find that two exponents, \texttt{0x6b8a5ae7} and \texttt{0x4042c3955}, are relatively prime, i.e.,

-a_ie_i + a_je_j = \texttt{-0xe860d9d9*0x6b8a5ae7 + 0x184e2990*0x4042c3955} = 1.


(m^{e_i})^{-a_i}\cdot (m^{e_j})^{a_j} = (c_i^{-1})^{a_i}\cdot(c_j)^{a_j} = m.

This could be realized in code in the following way:

def egcd(a, b):
   if a == 0:
       return (b, 0, 1)
       g, y, x = egcd(b % a, a)
       return (g, x - (b // a) * y, y)

def modinv(a, m):
   g, x, y = egcd(a, m)
   if g != 1:
       raise Exception('modular inverse does not exist')
       return x % m

def modexp(a, n, m):
	bits = []
	while n:
		n /= 2
	solution = 1
	for x in bits:
		solution = (solution*solution)%m
		if x:
			solution = (solution*a)%m
	return solution

A = 0x6fdcbfb5cd2cacd032ef7200fd49b9f304a6dbd8399f4a91a72d1d9150f97b3b513f44dfc56f6f7c8ec41a8ef9b93a80230a1e65e29d2ef519bb83931d4b0c7a589059cfdf2d571660ab790a9c7e085e3018bf19748abd6d521952b68bc9594c1ad34726658bd9bd445d3b6381ceee57328838e8a129867e505be0ca0d1a1da5L

B = 0x8caeaa7d272f9606fee9222efd1d922143db738b95bd64746b27bc4c0fd979a2c57b4735131a4391a81bf5f0c0c8eea41d4f91bed4d17784b1956fd89882b97c98009051ac3a03964499c864524d3ddc10299c0290e91707b62ce89b118afe558151be39d61de0483def52c6cb546132ecab85143715bc593a2892b1e41b37b9L

N = 0xa5f7f8aaa82921f70aad9ece4eb77b62112f51ac2be75910b3137a28d22d7ef3be3d734dabb9d853221f1a17b1afb956a50236a7e858569cdfec3edf350e1f88ad13c1efdd1e98b151ce2a207e5d8b6ab31c2b66e6114b1d5384c5fa0aad92cc079965d4127339847477877d0a057335e2a761562d2d56f1bebb21374b729743L

exp1 = 0x6b8a5ae7
exp2 = 0x4042c3955

_,x,y = egcd(exp1,exp2)
print hex((modexp(modinv(A,N),-x, N) * modexp(B,y, N) ) % N)

from which we obtain


or in ascii ‘flag_Strength_Lies_In_Differences’.

Understanding the disclosure attack

Techniques for providing anonymity in communication has a long history. In the 1980’s, David Chaum published novel techniques based on mix networks (or mixnets), which had several positive ramifications on cryptography as a whole. A mixnet can be described as a box, which accepts messages from multiple senders. The messages are shuffled, and then propagated through the network in random order to the recipients.


An n-to-n mixnet.

Assume that a user, Alice, wants to send a message M through a mixnet. Then, the following procedure is performed.

  1. Introduce randomness R_0 to the message.
  2. Encrypt the message (including the randomness R_0) using the public key K of the recipient.
  3. Include the address of the recipient, denoted A and some additional randomness R_1.
  4. Encrypt what is obtained in the previous step with the public key K_m of the mixnet.

The message that Alice sends then is E_{K_1}(R_1,E_K(R_0,M),A). The following is then performed by the mixnet:

  1. The mixnet decrypts using its private key.
  2. The mixnet removes randomness R_1.
  3. Extracts the adress of the recipient, i.e., A, and sends E_K(R_0,M) to that address.

The purpose of the randomness R_0 is to avoid direct guessing attacks on the encryption used between sender and recipient – for instance, if the mixnet is malicious. Moreover, the randomness R_1 asserts that the address A remains known only to the mixnet, Alice and obviously, the recipient. The use of mixnets can, and probably should, be iterated in several steps.

The disclosure attack is an attack that targets anonymity systems based on Chaum mixnets and was introduced by Kedogan, Agrawal and Penz in their seminal paper [1]. The adversary is given access to observe incoming and outgoing messages and which senders and recipients that are act in the communication.

The attack is performed under the assumption that a user Alice has m partners which are regularly communicated with, and the aim is to unravel the recipients. Denote the total number of users in the system N, the number of senders in each batch is denoted b (where 1<b<N), and the number of recipients in a batch is denoted n. All senders in a batch are assumed to be distinct, i.e., a sender can only send one message. Then, n \leq b since more than one sender can send messages to the same recipient. It is assumed that all senders uniformly chooses their recipient among the set of their partners in each communication.

The attack is divided into two phases, the learning phase and the excluding phase.

  1. In the learning phase the adversary records all receivers in a batch when a message from Alice is sent. This set of recipients is denoted by \mathcal R_i for some 0 < i \leq m.

    Whenever Alice is active, the recipients are recorded and put into \mathcal R_t. .

    The process is repeated until the adversay as m mutually disjoint sets, i.e., until

    \mathcal R_i \cap \mathcal R_j = \emptyset, \quad \forall i \neq j.

    Provided that we obtain m sets, each set \mathcal R_i contains one and only one partner of Alice. Here is a pitfall: if the sets are sampled sequentially, some set may contain two of Alice’s partners and we will not be able to find m sets.

    Expressed in Python code, it looks something like the following.

    # The universe of all possible destination addresses
    U = set(xrange(N))
    # Alice's communicating partners
    P = set(random.sample(U,m))
    # Pick (with duplicates) a random set with at least one element from P
    R = set(random.sample(P,1)).union(set([random.randint(0,N-1) for i in xrange(n-1)]))
    # Begin learning phase
    list_of_R = [R]
    flag = 1
    for i in xrange(m-1):
        while 1:
            R = set(random.sample(P,1)).union(set([random.randint(0,N-1) for i in xrange(n-1)]))
            flag = 0
            for L in list_of_R:
                if len(L.intersection(R)) != 0:
                    flag = 1
            if flag == 0:
  2. The attack now proceeds to the excluding phase. A new observation \mathcal R is recorded (again, when Alice is known to communicate). If the following is satisfied

    \mathcal R \cap \mathcal R_i \neq \emptyset and \mathcal R \cap \mathcal R_j = \emptyset, \quad \forall i \neq j,

    then \mathcal R_i is replaced by \mathcal R \cap \mathcal R_i. With high probability, this is reduce the cardinality of \mathcal R_i. This procedure is repeated until all sets \mathcal R_i, 0 < i \leq m have cardinality 1, i.e., contain only one recipient. Of course, since all sets were disjoint, the communicating parters of Alice have been unraveled.

    Again, expressed in Python code, we have the following.

    # Excluding phase
    oflag = 1
    while oflag == 1:
        oflag = 0
        flag = 1
        for i in xrange(m):
            R = set(random.sample(P,1)).union(set([random.randint(0,N-1) for k in xrange(n-1)]))
            L = list_of_R[i]
            if len(L.intersection(R)) != 0:
                flag = 0
                for j in set(xrange(m)).difference({i}):
                    if len(list_of_R[j].intersection(R)) != 0:
                        flag = 1
                if flag == 0:
                    list_of_R[i] = L.intersection(R)
            if len(list_of_R[i]) &gt; 1:
                oflag = 1
    # Verify that the found set is the set P
    print P == set.union(*list_of_R)

There is an obvious limitation to the attack. If

m > \lfloor N/m \rfloor,

then it is not possible to find m disjoints sets in the learning phase.

Another take at a disclosure attack

Under the assumptions from before, it is very simple to formulate a statistical attack that is much simpler to execute (and is considerably faster).

By using the recorded observations (when Alice communicates), we may simple make a histogram of the communication in the batches. Let c be the number of batches recorded, then the expected number of recorded communications with a non-parter of Alice is c(n-1)/N, while for a partner it is c(1/m + (n-1)/N).

In the below graph, c = 1000, n = 9, m = 9. Clearly, determining the communicating partners of Alice is not hard.


This very simple attack construction performs better than [1] and does also work for m > \lfloor N/m \rfloor. The assumptions made in [1] are also a bit unrealistic, in particular the assumption about a uniform recipient distribution among all other communicating parties.

[1] D. Kedogan, D. Agrawal, and S. Penz. Limits of anonymity in open environments. In Revised Papers from the 5th International Workshop on Information Hiding, volume 2578 of Lecture Notes in Computer Science, pages 53–69. Springer-Verlag, 2002.

Proving hardness of The Plauge’s problem

Yesterday, I found a quite exciting problem, which can be used to construct a public-key cryptosystem. The problem is as follows: given an undirected graph G = (V,E), partition the graph into disjoint partitions such that each partition contains exactly one node, which we will denote ‘middle node’, and all nodes being adjacent to the middle node. For a more detailed description, see [1].

It was posed as a question in [1] if the problem is NP-complete or not. We show (a bit informally) that the decision version of the problem is equivalent to the decision version of 3-SAT. For an arbitrary number of clauses, we construct subgraphs in the following way:

Here, the 3-SAT formula is (a \lor b \lor c)(\neg a \lor d \lor e)(\neg b \lor \neg d \lor c). The black nodes are forced to be middle nodes, and therefore either a green or a red node must be middle node. To provide dependence among variables, the variables must be linked at least once using operator-subgraphs. These are shown as dashed lines. The long-dashed lines are connected using Equality graphs, while the short-dashed are connected with Negation graphs. For instance, if we set a = \textsf{true}, then the same variable the remaining clauses must be forced to a = \textsf{true}. Below, we see the graphs that provide that operation.

For completeness, we provide nodes for basic logic operations in the graph representation. Since we by definition have no two-input logical operations in 3-SAT, these are not used in the reduction.

The colored nodes are ‘connector nodes’ which will be replaced by the nodes at the end of the dashed lines. If a partition is found, then it must necessarily be a solution to the 3-SAT formula. We will not prove this, but we advise the reader verify the claim for the simple graph. It is then hopefully easy and enough convincing to see that the graph construction can be generalized to any 3-SAT formula. The Or-operator is quite complex and is satisfiable if and only if at least one of the inputs are true. It is as follows:

The purpose of the Or-graph is to assert that at least one of the literals in each clause is true. If not, then the Or-graph is not possible to partition properly. So if there exists at least one clause that is no satisfiable, then an oracle for 3-SAT should output \textsf{No}. Likewise, the oracle for The Plague’s problem will output \textsf{No}. Our reduction is complete.

To prove that the reduction is polynomial, we note that the number of edges grows only linearly with the number of clauses. For the reverse reduction, see [1].


A New Algorithm for Solving Ring-LPN with a Reducible Polynomial

The LPN (Learning Parity with Noise) problem has recently proved to be of great importance in cryptology. A special and very useful case is the Ring-LPN problem, which typically provides improved efficiency in the constructed cryptographic primitive. We present a new algorithm for solving the Ring-LPN problem in the case when the polynomial used is reducible. It greatly outperforms previous algorithms for solving this problem. Using the algorithm, we can break the Lapin authentication protocol for the proposed instance using a reducible polynomial, in about 2^{70} bit operations.

A note on the security of hHB

A couple of days ago, a modification to the HB+ protocol was proposed [1] on ePrint. The proposal, called the hHB protocol, is an attempt to repair the man-in-the-middle vurnerability of HB+, in which the author is claiming to offer a provable security against these kinds of attacks. We show that there exists a trivial method to partially obtain the shared secret vectors.

In each round of hHB, the reader chooses a random vector {x} \leftarrow^{\$} \{0,1\}^k. To transfer secret vector {x}=x_1x_2...x_k to the tag, it uses a function f(\lambda_1,\lambda_2,\lambda_3), the shared secret {s} and random coins. This procedure is given below.

Assuming that the random bits of {x}=x_1x_2...x_k were successfully transferred to the tag, the following is performed to complete the authentication.

According to the author, this will ensure that no man-in-the-middle attacks are possible. Although the non-constant vector {x} makes the GRS-attack on the vector {a} cumbersome, we can still make a slight modification of the attack.

The initial step is to pertube the first position of b, i.e., b_1 \leftarrow b_1 \oplus \delta. We the run the protocol r times until we obtain a \textsf{accept} or \textsf{reject}, based on some threshold parameter. From this line of execution, we can decide the value of y_1. Repeating the process k-1 gives us the secret vector y=y_1y_2...y_k.

Thwarting the attack

Assuming that the protocol keeps the integrity of x and s via the function f, we can form a new secret vector t, and generate y from t in the same way that x is generated from s. This would further increase the transmission complexity of the protocol by a factor 2.


Let us now assume that we know y. Assume that we are sending bit j of the vector x. The function f sends some permutation of {(c_1,t_1),(c_2,t_2),(c_3,t_3)}, where each c_i \leftarrow^\$ \{0,1\}^k. However, we do not care which permutation.

Function f
The inverse function f^{-1} is defined as follows.
Inverse of function f

Let us pick the first position of the c_i-vectors and pertube that position for each c_i. This means that if that particular position s_i in the secret is non-zero, then x will take a uniformly random value in the current position j. If we do it for all positions, then we can test it against the verifier and thus obtain the first bit of s.


Berlekamp-Massey algorithm for binary fields in Python

For the course in Design of Digital Circuits.

# BM algorithm \
max_poly_len 	= 64
polyCD  		= [0]*max_poly_len
polyCpD 		= [0]*max_poly_len
polyTD  		= [0]*max_poly_len
desired_seq		= '10011101'

# functions to help with doing various stuff
def trunc(monomial_deg): 		return '1' if monomial_deg == 0 else 'D^'+str(monomial_deg)
def print_poly(poly_var): 		return  ''.join([trunc(x)+'  ' for x, e in enumerate(poly_var) if e != 0])
def parse_seq(poly_var): 		return [int(x) for x in poly_var]
def discrepancy(seq,polyCD,i): 	return sum([seq[i-j]&polyCD[j] for j in range(0,L+1)])%2
def add_poly(poly_a,poly_b): 	return [poly_a[j]^poly_b[j] for j in range(0,max_poly_len)]
def print_line():				print  ''.join(['-']*40)

# init
polyCD[0] 		= 1
polyCpD[0] 		= 1
polySeq 		= parse_seq(desired_seq)
L				= 0
l				= 1

# main loop
for i in range(0, len(desired_seq)):
	d = discrepancy(polySeq,polyCD,i)
	if d != 0:
		polyTD = polyCD
		polyCD =  add_poly(polyCD,[0]*l+polyCpD)
		if 2*L <= i:
			L = i+1-L
			l = 1
			polyCpD = polyTD
			l += 1
		l += 1
	# printout
	print 'i='+str(i),'s_i='+desired_seq[i],'d='+str(d),\

Stern’s algorithm: A short introduction

Stern’s algorithm is an algorithm for solving the following:

\blacksquare ~ \textnormal{\textbf{Problem} \textsc{General Decoding}}
Given a random matrix \mathbf{A} \in \mathbb{F}_2^{k\times n} and a pertubed vector \mathbf{r}, find a vector \mathbf{x} = (x_1,x_2,\ldots,x_{k}) such that \mathbf{x}\cdot\mathbf{A} = \mathbf{y} = (y_1,y_2,\ldots,y_n) and \mathbf{r} = (r_1,r_2,\ldots,r_n) agrees in as many points as possible.

\blacksquare ~ \textnormal{\textbf{Algorithm} \emph{Stern's algorithm}}
Input: generator matrix \mathbf{G}

  1. Pick a random column permutation \pi and permute \mathbf{G}.
  2. Make \mathbf{G} systematic.
  3. Pick all possible sums of p/2 columns from the k/2 first rows of \mathbf{G} and store in list \mathcal{L} indexed by bits in the q-field.
  4. Same as above but with the next k/2 rows of \mathbf{G}. Look in \mathcal{L} for values indexed by the q-field. For each such collision, create the sum of the two vectors. Now they form a vector stemming from the p columns in the first the k columns that is zero in the q-field.
  5. For each such candidate, calculate the whole weight. If it is w, output it. If none is found, repeat from 1.

The description here is a bit short and the reader is advised to read this post on information-set decoding.

New paper on low-weight polynomial multiples published.

Abstract In this paper we present an algorithm for finding low-weight multiples of polynomials over the binary field using coding theoretic methods. The code defined by the public polynomial is cyclic, allowing an attacker to search for any shift of the sought codeword. Therefore, a code with higher length and dimension is used, having a larger number of low-weight codewords. Additionally, since the degree of the sought polynomial is known, the sought codewords of weight w are transformed by a linear mapping into codewords of weight w − 2. Applying an algorithm for finding low-weight codewords on the constructed code yields complexity for a key-recovery attack against TCHo that is lower than previously expected. 

Available here.