AES-256 keyspace collision threshold calculator

test-keyspace.c

// OBJECTIVE: Find the smallest ASCII-only password length guaranteed to
// trigger KDF collisions for AES-256
// TEST 1 (binary ASCII): Find the smallest N for which:
//   2^7 + 2^14 + 2^21 + ... + 2^(7*N) > 2^256
// TEST 2 (printable ASCII): Find the smallest N for which:
//   95^1 + 95^2 + 95^3 + ... + 95^N > 2^256
// TEST 3 (alphanumeric ASCII): Find the smallest N for which:
//   62^1 + 62^2 + 62^3 + ... + 62^N > 2^256
// COMPILE:
//   gcc -o test-keyspace test-keyspace.c -lgmp

#include <stdio.h>
#include <gmp.h>

void fputmpz(char *fmt, int i, mpz_t num) {
  fprintf(stdout, fmt, i);
  mpz_out_str(stdout, 10, num);
  fputc('\r', stdout);
}

int main() {
  mpz_t target, accum, intermediate, const_2;

  mpz_init(target);
  mpz_init(accum);
  mpz_init(intermediate);
  mpz_init(const_2);

  mpz_set_ui(const_2, 2);
  mpz_pow_ui(target, const_2, 256);
  fputmpz("Target (2^%d): ", 256, target);
  fputc('\n', stdout);

  puts("\n===== TEST 1 (binary ASCII, 2^7N) =====");
  mpz_set_ui(accum, 0);
  for (int i=0; ; i++) {
    mpz_pow_ui(intermediate, const_2, 7*i);
    mpz_add(accum, accum, intermediate);
    if (mpz_cmp(accum, target) > 0) {
      // We've busted the limit
      fputmpz("%2d chars FAIL : ", i, accum);
      break;
    } else {
      fputmpz("%2d chars OK   : ", i, accum);
    }
  }
  fputc('\n', stdout);

  puts("\n===== TEST 2 (printable ASCII, 95^N) =====");
  mpz_t const_95;
  mpz_init(const_95);
  mpz_set_ui(const_95, 95);
  mpz_set_ui(accum, 0);
  for (int i=0; ; i++) {
    mpz_pow_ui(intermediate, const_95, i);
    mpz_add(accum, accum, intermediate);
    if (mpz_cmp(accum, target) > 0) {
      // We've busted the limit
      fputmpz("%2d chars FAIL : ", i, accum);
      break;
    } else {
      fputmpz("%2d chars OK   : ", i, accum);
    }
  }
  fputc('\n', stdout);
  mpz_clear(const_95);

  puts("\n===== TEST 3 (alphanumeric ASCII, 62^N) =====");
  mpz_t const_62;
  mpz_init(const_62);
  mpz_set_ui(const_62, 62);
  mpz_set_ui(accum, 0);
  for (int i=0; ; i++) {
    mpz_pow_ui(intermediate, const_62, i);
    mpz_add(accum, accum, intermediate);
    if (mpz_cmp(accum, target) > 0) {
      // We've busted the limit
      fputmpz("%2d chars FAIL : ", i, accum);
      break;
    } else {
      fputmpz("%2d chars OK   : ", i, accum);
    }
  }
  fputc('\n', stdout);
  mpz_clear(const_62);

  mpz_clear(target);
  mpz_clear(accum);
  mpz_clear(intermediate);
  mpz_clear(const_2);
}