• Stars
    star
    147
  • Rank 251,347 (Top 5 %)
  • Language
    C
  • Created over 14 years ago
  • Updated over 7 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Checking that functions are constant time with Valgrind
Checking that functions are constant time with Valgrind.

Information leaks via timing side channels can be deadly. You can steal RSA keys from other processes on the same host [1], extract the kernel's dm_crypt keys [2] and steal AES keys over the network [3].

In order for a function to be constant time, the branches taken and memory addresses accessed must be independent of any secret inputs. (That's assuming that the fundamental processor instructions are constant time, but that's true for all sane CPUs.)

However, it's tough to write constant time functions. You can the source to a few simple ones in [4]. Sometimes the design of the function is fundamentally flawed (like AES), but even when the function can be efficiently implemented in a constant time fashion, it's easy to slip up. Careful code review is currently the best practice but it's error prone as the amount of code increases and fragile in the face of change.

A type system could probably help here, but that's not the path I'm taking today. Since cryptographic functions result in abnormally straight line code, it's common for a typical input to exercise every instruction. So a tool like Valgrind could check all the branches and memory accesses to make sure that they haven't been tainted with secret data.

This would mean keeping track of every bit in memory to know if it's secret or not, likewise for all the CPU registers. Preferably at the bit level. The tool would also have to know that adding secret and non-secret data results in secret data etc. That suggests that it would be quite a complex tool.

But memcheck already does this! In order to keep track of uninitialised data it shadows every bit of memory and will warn you if you use uninitialised data in a branch or to index a memory access. So if we could tell memcheck to treat our secret data as uninitialised, everything should just work.

The valgrind patch does just that (against SVN r11097). It will intercept any calls to ct_poison and ct_unpoison in libctgrind.so*.

Let's look at a bad way to test a 128-bit MAC against a calculated value:

char check16_bad(unsigned char *a, unsigned char *b) {
  unsigned i;
  for (i = 0; i < 16; i++) {
    if (a[i] != b[i])
      return 0;
  }

  return 1;
}

And now, testing it with memcheck/ctgrind:

int
main() {
  unsigned char a[16], b[16];

  memset(a, 42, sizeof(a));
  memset(b, 42, sizeof(b));

  ct_poison(a, sizeof(a));

  printf("check16_bad\n");
  check16_bad(a, b);

  return 0;
}

$ /home/agl/devel/valgrind/vg-in-place ./a.out
...
check16_bad
==30993== Conditional jump or move depends on uninitialised value(s)
==30993==    at 0x40067F: check16_bad (test.c:11)
==30993==    by 0x40075F: main (test.c:44)

It seems to work! There are a few other tests in test.c which show the correct way to implement that function and well as a demo to show that secret dependent memory accesses are also caught by this tool.

We can test a few other things too. It confirms that donna-c64 [5] is constant time, which is nice. I also tested BN_mod_exp_mont_consttime from OpenSSL since that's a large function which calls functions from several other files.

It turns out not to be constant time! There's a secret dependent memory access:

==31076== Use of uninitialised value of size 8
==31076==    at 0x402210: MOD_EXP_CTIME_COPY_FROM_PREBUF (bn_exp.c:554)
==31076==    by 0x40277B: BN_mod_exp_mont_consttime (bn_exp.c:703)
==31076==    by 0x4011FF: main (ossl.c:24)

From inspection of the code, this appears to be a true positive. To be fair, the comment above the function suggests that it's rather misnamed:

/* This variant of BN_mod_exp_mont() uses fixed windows and the special
 * precomputation memory layout to limit data-dependency to a minimum
 * to protect secret exponents

It only claims to "limit" the side-channel leaks. I don't know how serious this is, but then you never do till someone gets a paper published by stealing all your secrets.


[1] http://www.daemonology.net/papers/htt.pdf
[2] http://www.springerlink.com/content/73876v1qq07q0277/ (paywall)
[3] http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
[4] http://golang.org/src/pkg/crypto/subtle/constant_time.go
[5] http://code.google.com/p/curve25519-donna/

More Repositories

1

pond

Pond
Go
910
star
2

xmpp-client

An XMPP client with OTR support
Go
366
star
3

curve25519-donna

Implementations of a fast Elliptic-curve Diffie-Hellman primitive
C
323
star
4

critbit

Critbit trees in C
C
319
star
5

ed25519

ed25519 for Go
179
star
6

crlset-tools

Tools for dealing with Chrome's CRLSets
Go
137
star
7

extract-nss-root-certs

Go
134
star
8

dnssec-tls-tools

DNSSEC/TLS tools
Python
35
star
9

dnscurve

Tools for DNS curve implementation
C
23
star
10

certificatetransparency

Certificate Transparency stuff
Go
18
star
11

rwb0fuz1024

This is example code for a Rabin-Williams public-key signature scheme designed to provide high speed verification and small signatures.
C
16
star
12

shamirsplit

The shamirsplit package implements Shamir's cryptographic secret sharing algorithm
Go
16
star
13

libdjb

A massaging of DJB's various client libraries into something that's easy to build and use
C
14
star
14

dclxvi

Naehrig, Niederhagen and Schwabe's pairings code, massaged into a shared library.
Assembly
12
star
15

obstcp

Obfuscated TCP
C
11
star
16

gcmsiv

draft-irtf-cfrg-gcmsiv-00
Go
11
star
17

nullok

Scripts that I used to write a blog post about section 7.24.1(2) of C11
Shell
10
star
18

local-dns-cache

DJB's dnscache made to play nicely with modern distributions
C
10
star
19

panda

PANDA key agreement experiment
Go
8
star
20

transport-security-state-generate

7
star
21

lsmsb

Linux Security Modules based sandboxing scheme
C++
7
star
22

tlsclient

C++
5
star
23

cfrgcurve

CFRG document on elliptic curves
XSLT
5
star
24

tls-chacha20poly1305

IETF draft for ChaCha20+Poly1305 in TLS
HTML
4
star
25

tls-padding

TLS padding draft
XML
4
star
26

harfbuzz

Harfbuzz is a unification of the shaping engines from Pango and Qt4 (fork)
3
star
27

spdy-compliance

SPDY compliance tests (mirror)
Go
3
star
28

aweb

Literate programming scheme targetting C and HTML
Haskell
3
star
29

ACVP-wiki

3
star
30

jbig2enc

JBIG2 Encoder
C++
3
star
31

otc

OpenType Condom
C++
2
star
32

technotes

Automatically exported from code.google.com/p/technotes
HTML
1
star
33

pkits-go

PKI testsuite for Go.
Go
1
star