matasano-cryptopals-go

My attempt at solving the Matasano Cryptopals challenges in Go
Log | Files | Refs

commit 05175ba70ee2aa90dcd5147fbd69244c95b6382e
parent 0f4c9014dfeb190f58832dcd283ea3943d23d6a5
Author: Dionysis Grigoropoulos <dgrig@erethon.com>
Date:   Tue, 19 Jun 2018 23:02:08 +0300

set_1: Implement tests and solutions for set one

Diffstat:
set_1.go | 170+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
set_1_test.go | 106+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 276 insertions(+), 0 deletions(-)

diff --git a/set_1.go b/set_1.go @@ -0,0 +1,170 @@ +package cryptopals + +import ( + "crypto/cipher" + "encoding/base64" + "encoding/hex" + "io/ioutil" + "math" + "math/bits" +) + +func hexStringToB64(input string) (string, error) { + out, err := hex.DecodeString(input) + if err != nil { + return "", err + } + return base64.StdEncoding.EncodeToString(out), nil +} + +func calculateFreqIndex(input []byte) []float64 { + var counts = make([]int, 256) + var freq = make([]float64, 256) + charCount := float64(0) + + for _, val := range input { + counts[val] += 1 + charCount++ + } + for index, val := range counts { + freq[index] = float64(val) / charCount + } + + return freq +} + +func scoreText(base, target []float64) float64 { + score := float64(0) + for index := range base { + score += math.Abs(base[index] - target[index]) + } + + return score +} + +func singleByteXOR(input []byte, key byte) []byte { + output := make([]byte, len(input)) + for i, c := range input { + output[i] = c ^ key + } + return output +} + +func bruteXOR(cipher []byte) ([]byte, byte, float64) { + data, err := ioutil.ReadFile("data/pride.txt") + if err != nil { + panic("Failed to read file!") + } + freqIndex := calculateFreqIndex(data) + var output []byte + var key byte + score := float64(1000000) + for i := 0; i < 256; i++ { + tmpOutput := singleByteXOR(cipher, byte(i)) + tmpScore := scoreText(freqIndex, calculateFreqIndex(tmpOutput)) + if tmpScore < score { + score = tmpScore + output = tmpOutput + key = byte(i) + } + } + return output, key, score +} + +func xorByteSlices(a, b []byte) []byte { + if len(a) != len(b) { + panic("Byte Slices of unequal lengths") + } + output := make([]byte, len(a)) + for i := range a { + output[i] = a[i] ^ b[i] + } + return output +} + +func hexStringDecode(s string) []byte { + bytes, err := hex.DecodeString(s) + if err != nil { + panic("Failed to decode hex") + } + return bytes +} + +func repeatingXOR(plain, key []byte) []byte { + output := make([]byte, len(plain)) + rkey := make([]byte, 0) + + for len(rkey) < len(plain) { + rkey = append(rkey, key...) + } + for i := range plain { + output[i] = plain[i] ^ rkey[i] + } + return output +} + +func hammingDistanceBytes(a, b []byte) int { + var distance int = 0 + for index := range a { + distance += bits.OnesCount8(a[index] ^ b[index]) + } + return distance +} + +func findRepeatingXORKeySize(cipher []byte) int { + score := float64(10000000) + var size int + for keySize := 2; keySize < 40; keySize++ { + f, s := cipher[:keySize*4], cipher[keySize*4:keySize*2*4] + tmpScore := float64(hammingDistanceBytes(f, s)) / float64(keySize*4) + if tmpScore < score { + score = tmpScore + size = keySize + } + } + return size +} + +func breakRepeatingXOR(cipher []byte) []byte { + keySize := findRepeatingXORKeySize(cipher) + key := make([]byte, keySize) + block := make([]byte, (len(cipher)+keySize-1)/keySize) + for c := 0; c < keySize; c++ { + for index := range block { + if index*keySize+c >= len(cipher) { + continue + } + block[index] = cipher[index*keySize+c] + } + _, char, _ := bruteXOR(block) + key[c] = char + } + return key +} + +func decryptAES128ECB(cipher []byte, block cipher.Block) []byte { + blockSize := block.BlockSize() + if len(cipher)%blockSize != 0 { + panic("Cipher size must be a multiple of key size") + } + output := make([]byte, len(cipher)) + for i := 0; i < len(cipher); i += blockSize { + block.Decrypt(output[i:], cipher[i:]) + } + return output +} + +func detectECB(cipher []byte, size int) bool { + if len(cipher)%size != 0 { + panic("Cipher size must be a multiple of key size") + } + detected := make(map[string]bool) + for i := 0; i < len(cipher); i += size { + out := string(cipher[i : i+size]) + if detected[out] { + return true + } + detected[out] = true + } + return false +} diff --git a/set_1_test.go b/set_1_test.go @@ -0,0 +1,106 @@ +package cryptopals + +import ( + "bufio" + "bytes" + "crypto/aes" + "encoding/base64" + "fmt" + "io/ioutil" + "os" + "strings" + "testing" +) + +func TestProblem1(t *testing.T) { + output, err := hexStringToB64("49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d") + if err != nil { + t.Fatal(err) + } + if output != "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t" { + t.Fatal("Invalid response", output) + } +} + +func TestProblem2(t *testing.T) { + output := xorByteSlices(hexStringDecode("1c0111001f010100061a024b53535009181c"), hexStringDecode("686974207468652062756c6c277320657965")) + if !bytes.Equal(output, hexStringDecode("746865206b696420646f6e277420706c6179")) { + t.Errorf("xor not working! %x", output) + } +} + +func TestProblem3(t *testing.T) { + output, _, _ := bruteXOR(hexStringDecode("1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736")) + fmt.Printf("%s\n", output) +} + +func TestProblem4(t *testing.T) { + file, err := os.Open("data/4.txt") + if err != nil { + panic("Failed to read file!") + } + defer file.Close() + scanner := bufio.NewScanner(file) + + score := float64(1000000) + var output []byte + + for scanner.Scan() { + out, _, tmpScore := bruteXOR(hexStringDecode(scanner.Text())) + if tmpScore < score { + score = tmpScore + output = out + } + } + fmt.Printf("%s\n", output) +} + +func TestProblem5(t *testing.T) { + in := []byte(`Burning 'em, if you ain't quick and nimble +I go crazy when I hear a cymbal`) + out := repeatingXOR(in, []byte("ICE")) + if !bytes.Equal(out, hexStringDecode("0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f")) { + t.Error("wrong xor encryption: ", out) + } +} + +func TestHamming(t *testing.T) { + output := hammingDistanceBytes([]byte("this is a test"), []byte("wokka wokka!!!")) + if output != 37 { + t.Error("Hamming distance is not 37, it's:", output) + } +} + +func TestProblem6(t *testing.T) { + file, err := ioutil.ReadFile("data/6.txt") + if err != nil { + panic("Failed to read file!") + } + data := string(file) + text, _ := base64.StdEncoding.DecodeString(data) + fmt.Printf("Key is: '%s'\n", breakRepeatingXOR(text)) +} + +func TestProblem7(t *testing.T) { + file, err := ioutil.ReadFile("data/7.txt") + if err != nil { + panic("Failed to read file!") + } + data := string(file) + text, _ := base64.StdEncoding.DecodeString(data) + block, _ := aes.NewCipher([]byte("YELLOW SUBMARINE")) + fmt.Printf("Decrypted to: '%s'\n", decryptAES128ECB(text, block)[:10]) +} + +func TestProblem8(t *testing.T) { + file, err := ioutil.ReadFile("data/8.txt") + if err != nil { + panic("Failed to read file!") + } + data := string(file) + for index, line := range strings.Split(data, "\n") { + if detectECB(hexStringDecode(line), 16) { + fmt.Printf("Line number %d is encrypted with ECB mode\n", index) + } + } +}