What is the time complexity of crypt function in Linux?

Question

The crypt function described as below in unix for authentication:

char *crypt(const char *key, const char *salt);

Assume that I have the key (of length n), and the salt (of length m), what is the time complexity (order of algorithm) of calling this function?

Answer 1

From the man page of crypt:

salt is a two-character string chosen from the set [a-zA-Z0-9./]. This string is used to perturb the algorithm in one of 4096 different ways.

and

By taking the lowest 7 bits of each of the first eight characters of the key, a 56-bit key is obtained.

The thusly obtained key is then used to encrypt a constant string (using a tweaked DES algorithm), which takes constant time. Therefore, the function has constant run-time for any valid arguments. Note that this truncating leads to very weak passwords.

As commented by melpomene, some implementations provide an extension to the crypt function that allow selecting a more secure mode. For the following, I will assume you are using the crypt function from the GNU C library. The manual says:

For the MD5-based algorithm, the salt should consist of the string $1$, followed by up to 8 characters, terminated by either another $ or the end of the string. The result of crypt will be the salt, followed by a $ if the salt didn't end with one, followed by 22 characters from the alphabet ./0-9A-Za-z, up to 34 characters total. Every character in the key is significant.

Since the length of the salt is fixed by a constant and the cryptographic hash function has time complexity linear in the length of the input, the overall time complexity of the crypt function will be linear in key.

My version of glibc also supports the more secure SHA-256 (selected via $5$) and SHA-512 (selected via $6$) cryptographic hash functions in addition to MD5. These have linear time complexity in the length of their input, too.

Since I cannot make sense out of the task I'm actually supposed to do right now, I have timed the various crypt methods to support the above analysis. Here are the results.

Plotted are the execution times spent in the crypt function against the length of the key string. Each data series is overlayed with a linear regression except for DES where the average value is plotted instead. I am surprised that SHA-512 is actually faster than SHA-256.

The code used for the benchmarks is here (benchmark.c).

#define _GNU_SOURCE  /* crypt */

#include <errno.h>   /* errno, strerror */
#include <stdio.h>   /* FILE, fopen, fclose, fprintf */
#include <stdlib.h>  /* EXIT_{SUCCESS,FAILURE}, malloc, free, [s]rand */
#include <string.h>  /* size_t, strlen */
#include <assert.h>  /* assert */
#include <time.h>    /* CLOCKS_PER_SEC, clock_t, clock */
#include <unistd.h>  /* crypt */

/* Barrier to stop the compiler from re-ordering instructions. */
#define COMPILER_BARRIER asm volatile("" ::: "memory")

/* First character in the printable ASCII range. */
static const char ascii_first = ' ';

/* Last character in the printable ASCII range. */
static const char ascii_last = '~';

/*
  Benchmark the time it takes to crypt(3) a key of length *keylen* with salt
  *salt*.  The result is written to the stream *ostr* so its computation cannot
  be optimized away.
*/
static clock_t
measure_crypt(const size_t keylen, const char *const salt, FILE *const ostr)
{
  char * key;
  const char * passwd;
  clock_t t1;
  clock_t t2;
  size_t i;
  key = malloc(keylen + 1);
  if (key == NULL)
    return ((clock_t) -1);
  /*
    Generate a random key.  The randomness is extremely poor; never do this in
    cryptographic applications!
  */
  for (i = 0; i < keylen; ++i)
    key[i] = ascii_first + rand() % (ascii_last - ascii_first);
  key[keylen] = '\0';
  assert(strlen(key) == keylen);
  COMPILER_BARRIER;
  t1 = clock();
  COMPILER_BARRIER;
  passwd = crypt(key, salt);
  COMPILER_BARRIER;
  t2 = clock();
  COMPILER_BARRIER;
  fprintf(ostr, "%s\n", passwd);
  free(key);
  return t2 - t1;
}

/*
  The program can be called with zero or one arguments.  The argument, if
  given, will be used as salt.
*/
int
main(const int argc, const char *const *const argv)
{
  const size_t keymax = 2000;
  const size_t keystep = 100;
  const char * salt = "..";  /* default salt */
  FILE * devnull = NULL;  /* redirect noise to black hole */
  int status = EXIT_SUCCESS;
  size_t keylen;
  if (argc > 1)
    salt = argv[1];
  devnull = fopen("/dev/null", "r");
  if (devnull == NULL)
    goto label_catch;
  srand((unsigned) clock());
  for (keylen = 0; keylen <= keymax; keylen += keystep)
    {
      clock_t ticks;
      double millis;
      ticks= measure_crypt(keylen, salt, devnull);
      if (ticks < 0)
        goto label_catch;
      millis = 1.0E3 * ticks / CLOCKS_PER_SEC;
      fprintf(stdout, "%16zu %e\n", keylen, millis);
    }
  goto label_finally;
 label_catch:
  status = EXIT_FAILURE;
  fprintf(stderr, "error: %s\n", strerror(errno));
 label_finally:
  if (devnull != NULL)
    fclose(devnull);
  return status;
}

The Gnuplot script used for the regression and plotting is here (plot.gplt).

set terminal 'svg'
set output 'timings.svg'

set xrange [0 : *]
set yrange [0 : *]

set key top left

set title 'crypt(3) benchmarks'
set xlabel 'key length / bytes'
set ylabel 'computation time / milliseconds'

des(x) = a_des
md5(x) = a_md5 + b_md5 * x
sha256(x) = a_sha256 + b_sha256 * x
sha512(x) = a_sha512 + b_sha512 * x

fit des(x) 'timings.des' via a_des
fit md5(x) 'timings.md5' via a_md5, b_md5
fit sha256(x) 'timings.sha256' via a_sha256, b_sha256
fit sha512(x) 'timings.sha512' via a_sha512, b_sha512

plot des(x)           w l notitle     lc '#75507b' lt 1 lw 2.5,     \
     'timings.des'    w p t 'DES'     lc '#5c3566' pt 7 ps 0.8,     \
     md5(x)           w l notitle     lc '#cc0000' lt 1 lw 2.5,     \
     'timings.md5'    w p t 'MD5'     lc '#a40000' pt 7 ps 0.8,     \
     sha256(x)        w l notitle     lc '#73d216' lt 1 lw 2.5,     \
     'timings.sha256' w p t 'SHA-256' lc '#4e9a06' pt 7 ps 0.8,     \
     sha512(x)        w l notitle     lc '#3465a4' lt 1 lw 2.5,     \
     'timings.sha512' w p t 'SHA-512' lc '#204a87' pt 7 ps 0.8

Finally the Makefile used to hook everything together (GNUmakefile).

CC := gcc
CPPFLAGS :=
CFLAGS := -Wall -O2
LDFLAGS :=
LIBS := -lcrypt

all: benchmark timings.svg timings.png

benchmark: benchmark.o
    ${CC} -o $@ ${CFLAGS} $^ ${LDFLAGS} ${LIBS}

benchmark.o: benchmark.c
    ${CC} -c ${CPPFLAGS} ${CFLAGS} $<

timings.svg: plot.gplt timings.des timings.md5 timings.sha256 timings.sha512
    gnuplot $<

timings.png: timings.svg
    convert $< $@

timings.des: benchmark
    ./$< '$(shell pwgen -ncs 2)' > $@

timings.md5: benchmark
    ./$< '$$1$$$(shell pwgen -ncs 8)' > $@

timings.sha256: benchmark
    ./$< '$$5$$$(shell pwgen -ncs 16)' > $@

timings.sha512: benchmark
    ./$< '$$6$$$(shell pwgen -ncs 16)' > $@

clean:
    rm -f benchmark benchmark.o fit.log $(wildcard *.o timings.*)

.PHONY: all clean