Cryptography

Cryptography and Cryptanalysis are the art of creating and breaking codes.

This section will only explain the most common attacks, as there are too many of them (and would require too much time to write). However, tools and resources will be provided to help you learn more about cryptography and understand the well-known attacks.

Platforms with cryptanalysis challenges:

Common tools

• SageMath - Website

  Powerful mathematics software, very useful for crypto and number theory.

• Crypton - GitHub

  Archive repository of the most common attacks on cryptosystems.

• Crypto Attacks repository - GitHub

  A large collection of cryptography attacks.

Common attacks

• Predictable Pseudo-Random Number Generators

  For performance reasons, most of random number generators are predictable. Generating a cryptographic key requires a secure PRNG.

  For example, python’s random module uses the Mersenne Twister algorithm, which is not cryptographically secure. randcrack is a tool that can predict the next random number generated by the Mersenne Twister algorithm when you know the 624 previously generated integers (4 bytes each).

  Another common predictable generator is the Linear Congruential Generator.

  • Linear Congruential Generator

• Duplicate Signature Key Selection (DSKS) - StackExchange

  Given a message m and a signature s, it is possible to find a second signature s' generated from a different private/public key pair.

  This is valid for most of digital signature schemes, including RSA, DSA, ECDSA.

• Square root when $p ≡ 3$ mod $4$

  Computing the square root of a number modulo a prime number is easy when the prime is congruent to 3 modulo 4.

  Here is how to do it with SageMath:

  p = 101
  F = GF(p)
  sr = F(71).sqrt()
  assert sr**2 % p == 71

• Recovering a key constrained by logical rules with z3 - GitHub

  When the bits of a key (or plaintext) must satisfy a set of logical or arithmetic rules (parity of groups of bits, positional relations, palindromes, fixed popcount over a window, etc.), the key space is often reduced to a single candidate. Instead of reversing the constraints by hand, model them in an SMT solver like z3 and let it solve for the bits, then finish the challenge (for example by XORing the recovered key with the ciphertext).

  from z3 import *
  k = [BitVec(f"k_{i}", 1) for i in range(128)]
  s = Solver()
  for i in range(0, 128, 4):                     # example: each nibble has odd parity
      s.add(Sum([ZeroExt(7, k[i+j]) for j in range(4)]) % 2 == 1)
  assert s.check() == sat
  bits = [s.model()[b].as_long() for b in k]