Last week I wrapped up the chapter on the crypto package in Go, The Standard Library
Within the crypto package we have the crypto/subtle package. This package contains functions for doing constant time operations which are an important part of cryptography.
Constant time functions help prevent timing attacks which are caused when operations take different amounts of time to complete a task based on some input. When the time something takes leaks information about what's going on.
Comparing Strings
Let's look at a standard string comparison algorithm. For every character in a string, compare it to the character at the same index in the other string. If they are equal, try the next character. If not, return false. Pretty straight forward, but if the first character doesn't match, the function returns immediately. If the first character matches but the second doesn't, the function takes just a little bit longer. This difference is enough to measure, even on web applications. See these two papers for more on that. The functions in the crypto/subtle package use some bit twiddling to perform operations in a constant time.
Let's look at how this would work in Go:
| package main | |
| import ( | |
| "container/heap" | |
| "crypto/subtle" | |
| "flag" | |
| "log" | |
| T "testing" | |
| "time" | |
| ) | |
| var ( | |
| password = flag.String("password", "secret", "The password to try and guess") | |
| letters = []byte("abcdefghijklmnopqrstuvwxyz") | |
| compare = flag.String("compare", "broken", "The comparison function to use. Must be one of constant or broken (default)") | |
| ) | |
| type TestRun struct { | |
| Time int64 | |
| Byte byte | |
| } | |
| type Times []TestRun | |
| func (t Times) Len() int { return len(t) } | |
| func (t Times) Less(i, j int) bool { return t[i].Time > t[j].Time } | |
| func (t Times) Swap(i, j int) { t[i], t[j] = t[j], t[i] } | |
| func (t *Times) Push(v interface{}) { | |
| *t = append(*t, v.(TestRun)) | |
| } | |
| func (t *Times) Pop() interface{} { | |
| a := *t | |
| n := len(a) | |
| v := a[n-1] | |
| *t = a[0 : n-1] | |
| return v | |
| } | |
| type Compare func(x, y []byte) int | |
| func BrokenCompare(x, y []byte) int { | |
| for i := range x { | |
| if x[i] != y[i] { | |
| return 0 | |
| } | |
| } | |
| return 1 | |
| } | |
| func Crack(password []byte, comp Compare) []byte { | |
| n := len(password) | |
| guess := make([]byte, n) | |
| for index := range password { | |
| times := make(Times, 0) | |
| for _, letter := range letters { | |
| guess[index] = letter | |
| result := T.Benchmark(func(b *T.B) { | |
| for i := 0; i < b.N; i++ { | |
| comp(password, guess) | |
| } | |
| }) | |
| heap.Push(×, TestRun{ | |
| Time: result.NsPerOp(), | |
| Byte: letter, | |
| }) | |
| log.Printf("took %s (%d ns/op) to try %q for index %d", result.T, result.NsPerOp(), letter, index) | |
| } | |
| tr := heap.Pop(×).(TestRun) | |
| guess[index] = tr.Byte | |
| log.Printf("best guess is %q for index %d", tr.Byte, index) | |
| log.Printf("guess is now: %s", guess) | |
| } | |
| return guess | |
| } | |
| func ConstantTimeCrack(pw []byte) []byte { | |
| return Crack(pw, subtle.ConstantTimeCompare) | |
| } | |
| func BrokenCrack(pw []byte) []byte { | |
| return Crack(pw, BrokenCompare) | |
| } | |
| func main() { | |
| flag.Parse() | |
| var guess []byte | |
| pw := []byte(*password) | |
| start := time.Now() | |
| switch *compare { | |
| case "broken": | |
| guess = BrokenCrack(pw) | |
| case "constant": | |
| guess = ConstantTimeCrack(pw) | |
| default: | |
| log.Fatalf("%s is not a valid compare function. Must be one of broken or constant") | |
| } | |
| end := time.Now() | |
| dur := end.Sub(start) | |
| log.Printf("password guess after %s is: %s", dur, guess) | |
| } |
You can run this example with go run timing_attack.go -compare broken (output) and go run timing_attack.go -compare constant (output). In the broken form, we use the algorithm I described above. For each index, there is one letter that takes a noticeably longer amount of time. You can see the attack progress and eventually guess the password. Well, except for the last character, but when you get it down to one character it's pretty easy to figure out what it should be (especially in a case like the example). The timing differences in the constant time run are too small to worry about.
The call to comp(password, guess) could be anything. You could be hitting a web application's login action with your guess and then they'd be doing the comparison to password. I'm just calling the function to prove the point.
The More You Know
Cryptography is a tricky subject. Using constant time functions won't make everything crypto related you do magically work, but it's an important part nonetheless. For a better look at all things cryptography, I'd recommend Applied Cryptography by Bruce Schneier.
This example is from Go, The Standard Library. If you like it and want to support the book, head over to http://thestandardlibrary.com/ and get your copy. The book is in progress and I push updates as I go. Thanks for reading!