My solutions to the Cryptopals Challenges in Go.
The string:
49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d
Should produce:
SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t
So go ahead and make that happen. You’ll need to use this code for the rest of the exercises.
Always operate on raw bytes, never on encoded strings. Only use hex and base64 for pretty-printing.
package main
import (
"fmt"
"encoding/hex"
"encoding/base64"
"log"
)
func convertHexToBase64(src string) (string, error) {
// decode from hex
b, err := hex.DecodeString(src)
if err != nil {
return "", err
}
// encode to base64
return base64.StdEncoding.EncodeToString(b), nil
}
func main() {
src := "49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d"
dst, err := convertHexToBase64(src)
if err != nil {
log.Fatal(err)
}
fmt.Println("Base64 encoding:\n" , dst)
}Write a function that takes two equal-length buffers and produces their XOR combination.
If your function works properly, then when you feed it the string:
1c0111001f010100061a024b53535009181c
… after hex decoding, and when XOR’d against:
686974207468652062756c6c277320657965
… should produce:
746865206b696420646f6e277420706c6179
Note that this could be made more efficient by perform the XOR operation on something larger than bytes (i.e. uint64s) but for these exercises performance is not an issue.
package main
import (
"fmt"
"encoding/hex"
"log"
)
func xorHexStrings(a, b string) ([]byte, error) {
// decode from hex
aDecoded, err := hex.DecodeString(a)
if err != nil {
return nil, err
}
bDecoded, err := hex.DecodeString(b)
if err != nil {
return nil, err
}
// check that strings are same length
if len(aDecoded) != len(bDecoded) {
return nil, fmt.Errorf("hex strings are not equal length")
}
// XOR
d := make([]byte, len(aDecoded))
for i, _ := range d {
d[i] = aDecoded[i] ^ bDecoded[i]
}
return d, nil
}
func main() {
a := "1c0111001f010100061a024b53535009181c"
b := "686974207468652062756c6c277320657965"
dst, err := xorHexStrings(a, b)
if err != nil {
log.Fatal(err)
}
fmt.Printf("%x", dst)
}The hex encoded string:
1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736
… has been XOR’d against a single character. Find the key, decrypt the message.
You can do this by hand. But don’t: write code to do it for you.
How? Devise some method for “scoring” a piece of English plaintext. Character frequency is a good metric. Evaluate each output and choose the one with the best score.
You now have our permission to make “ETAOIN SHRDLU” jokes on Twitter.
The solution works but I admit freely that it could return an invalid result given another input. The method of “scoring” a deciphered result is crude. I take the frequency of characters in the English alphabet as a float score value and sum the scores of all characters in a given deciphering attempt. The highest scoring result is presented. Rather than have duplicate values in the scoring map present for upper and lowercase characters, I simply adjust the uppercase characters before assigning the score of their lowercase counterpart.
package main
import (
"fmt"
"encoding/hex"
"log"
)
var englishCharFrequency = map[byte]float32 {
97:8.34, // a
98:1.54, // b
99:2.73, // c
100:4.14, // d
101:12.60, // e
102:2.03, // f
103:1.92, // g
104:6.11, // h
105:6.71, // i
106:0.23, // j
107:0.87, // k
108:4.24, // l
109:2.53, // m
110:6.80, // n
111:7.70, // o
112:1.66, // p
113:0.09, // q
114:5.68, // r
115:6.11, // s
116:9.37, // t
117:2.85, // u
118:1.06, // v
119:2.34, // w
120:0.20, // x
121:2.04, // y
122:0.06, // z
}
func decode(src string, scoringMap map[byte]float32) (key byte, decoded []byte, err error) {
// decode from hex
d, err := hex.DecodeString(src)
if err != nil {
return byte(0), nil, err
}
decoded = make([]byte, len(d))
var score float32
// assume key is a single ascii character
for k := 0; k < 126; k++ {
var keyScore float32
// inverse the xor with this key and sum the score
for i, _ := range d {
d[i] ^= byte(k)
if d[i] < 91 {
// convert to lowercase for the purposes of scoring
keyScore += scoringMap[d[i]+32]
} else {
keyScore += scoringMap[d[i]]
}
}
// compare score with previous key
// if new score is higher replace the "best" key and decoding
if keyScore > score {
score = keyScore
key = byte(k)
copy(decoded, d)
}
}
return key, decoded, nil
}
func main() {
src := "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736"
key, decoded, err := decode(src, englishCharFrequency)
if err != nil {
log.Fatal(err)
}
fmt.Printf("key: %s\ndecoded message: %s\n", string([]byte{key}), string(decoded))
}One of the 60-character strings in this file (4.txt) has been encrypted by single-character XOR.
Find it.
(Your code from #3 should help.)
Since the instructions are a little unclear, I first just printed the lines from the file decoded from hex. I wanted to see if there were lines of English text and only one was encoded or if there were lines of gibberish and only one gibberish line could be decoded. It seemed to be the latter. The brute force approach is quite simple then. If we make the same assumptions as 1-3, we can iterate through each line and iterate through every possible key to find the resulting decoded message with the highest value based letter frequency in the English language. We should have a score associated with each line. We can just assume the highest score is the “real” one and that message was encoded with single-character XOR.
package main
import (
"fmt"
"log"
"encoding/hex"
"os"
"bufio"
)
// englishCharFrequency holds the ascii (or utf-8)
// byte value for lowercase letters in the English
// language along with their corresponding percentage
// frequency. To access the value of uppercase
// characters, one can just modify the byte value.
// Uppercase characters have values from 65 to 90.
// Lowercase characters have value from 97 to 122.
// All other values hold symbols that we wouldn't
// want to modify. So to get the frequency of an
// uppercase character, simply add 32 to the byte
// value before looking up in the map.
var englishCharFrequency = map[byte]float32 {
97:8.34, // a
98:1.54, // b
99:2.73, // c
100:4.14, // d
101:12.60, // e
102:2.03, // f
103:1.92, // g
104:6.11, // h
105:6.71, // i
106:0.23, // j
107:0.87, // k
108:4.24, // l
109:2.53, // m
110:6.80, // n
111:7.70, // o
112:1.66, // p
113:0.09, // q
114:5.68, // r
115:6.11, // s
116:9.37, // t
117:2.85, // u
118:1.06, // v
119:2.34, // w
120:0.20, // x
121:2.04, // y
122:0.06, // z
}
// readLines takes in a filepath and reads lines from it
// one-by-one (appending to an output list) until it
// reaches the end of the file. Before appending, each
// line is decoded from hex into a byte slice for easy
// operation later.
func readLines(path string) (lines [][]byte, err error) {
file, err := os.Open(path)
if err != nil {
return nil, err
}
scanner := bufio.NewScanner(file)
scanner.Split(bufio.ScanLines)
for scanner.Scan() {
decodedLine, err := hex.DecodeString(scanner.Text())
if err != nil {
return nil, err
}
lines = append(lines, decodedLine)
}
if err = scanner.Err(); err != nil {
return nil, err
}
return lines, nil
}
// scoreLine iterates through every possible ascii character
// and performs a single-char XOR operation on the input line.
// For each key character used, it checks if the output has a
// higher score (based on English character frequency) than the
// previous best. Finally it returns the key and decoded line
// with the highest value. We are more thorough than 1-3 and
// actually check full range of possible keys.
func scoreLine(line []byte, scoreMap map[byte]float32) (key byte, decoded []byte, score float32) {
decoded = make([]byte, len(line))
scratch := make([]byte, len(line))
for k := 32; k < 127; k++ {
copy(scratch, line)
var kScore float32
// single-char XOR and sum score
for i, _ := range scratch {
scratch[i] ^= byte(k)
if ((scratch[i] > 64) && (scratch[i] < 91)) {
// convert uppercase to lowercase
kScore += scoreMap[scratch[i]+32]
} else {
kScore += scoreMap[scratch[i]]
}
}
// compare score with previous key and supplant if higher
if kScore > score {
score = kScore
key = byte(k)
copy(decoded, scratch)
}
}
return key, decoded, score
}
// scoreLines scores each line by finding the single-char key
// for XOR cipher that results in the highest scoring (based
// on character frequency in English language).
func scoreLines(lines [][]byte, scoreMap map[byte]float32) (bestKey byte, decoded []byte, linum int) {
decoded = make([]byte, len(lines[0]))
var bestScore float32
for i, line := range lines {
key, scratch, score := scoreLine(line, scoreMap)
if score > bestScore {
bestScore = score
bestKey = key
copy(decoded, scratch)
linum = i
}
}
return
}
func main () {
path := "4.txt"
// read in the lines and decode from hex
lines, err := readLines(path)
if err != nil {
log.Fatal(err)
}
// score the lines finding the most likely
// encoded
bestKey, decoded, linum := scoreLines(lines, englishCharFrequency)
fmt.Printf("line %v was encoding via single-character XOR cipher with %s as the key. The decoded line is: %s\n", linum, string([]byte{bestKey}), string(decoded))
}Here is the opening stanza of an important work of the English language:
Burning ‘em, if you ain’t quick and nimble I go crazy when I hear a cymbal
Encrypt it, under the key “ICE”, using repeating-key XOR.
In repeating-key XOR, you’ll sequentially apply each byte of the key; the first byte of plaintext will be XOR’d against I, the next C, the next E, then I again for the 4th byte, and so on.
It should come out to:
0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272 a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f
Encrypt a bunch of stuff using your repeating-key XOR function. Encrypt your mail. Encrypt your password file. Your .sig file. Get a feel for it. I promise, we aren’t wasting your time with this.
package main
import (
"fmt"
)
func encrypt(src []byte, key []byte) {
for i, _ := range src {
src[i] ^= key[i%len(key)]
}
}
func main() {
src := "Burning 'em, if you ain't quick and nimble\nI go crazy when I hear a cymbal"
bSrc := []byte(src)
key := "ICE"
encrypt(bSrc, []byte(key))
fmt.Printf("%x", bSrc)
}This challenge isn’t conceptually hard, but it involves actual error-prone coding. The other challenges in this set are there to bring you up to speed. This one is there to qualify you. If you can do this one, you’re probably just fine up to Set 6.
There’s a file here (6.txt). It’s been base64’d after being encrypted with repeating-key XOR.
Decrypt it.
Here’s how:
Let KEYSIZE be the guessed length of the key; try values from 2 to (say) 40. Write a function to compute the edit distance/Hamming distance between two strings. The Hamming distance is just the number of differing bits. The distance between:
this is a test
and
wokka wokka!!!
is 37. Make sure your code agrees before you proceed. For each KEYSIZE, take the first KEYSIZE worth of bytes, and the second KEYSIZE worth of bytes, and find the edit distance between them. Normalize this result by dividing by KEYSIZE. The KEYSIZE with the smallest normalized edit distance is probably the key. You could proceed perhaps with the smallest 2-3 KEYSIZE values. Or take 4 KEYSIZE blocks instead of 2 and average the distances. Now that you probably know the KEYSIZE: break the ciphertext into blocks of KEYSIZE length. Now transpose the blocks: make a block that is the first byte of every block, and a block that is the second byte of every block, and so on. Solve each block as if it was single-character XOR. You already have code to do this. For each block, the single-byte XOR key that produces the best looking histogram is the repeating-key XOR key byte for that block. Put them together and you have the key.
This code is going to turn out to be surprisingly useful later on. Breaking repeating-key XOR (“Vigenere”) statistically is obviously an academic exercise, a “Crypto 101” thing. But more people “know how” to break it than can actually break it, and a similar technique breaks something much more important.
We get more tech support questions for this challenge than any of the other ones. We promise, there aren’t any blatant errors in this text. In particular: the “wokka wokka!!!” edit distance really is 37.
First we need to write a method that can compute the Hamming distance between two strings.
The Hamming distance is the number of differing bits.
We can find this by counting the number of set bits after XORing the two strings.
This can be done manually by shifting a mask and checking in bit in each byte.
Alternatively, we can use the math/bits bit counting methods.
package main
import (
"fmt"
"log"
"math/bits"
)
func hammingDist(strOne, strTwo []byte) (dist int, err error) {
if len(strOne) != len(strTwo) {
return dist, fmt.Errorf("hamming distance can not be calculated for strings of differing length")
}
var scratch byte
for i, _ := range strOne {
scratch = strOne[i] ^ strTwo[i]
for j := 0; j < 8; j++ {
if scratch & (1 << j) > 0 {
dist++
}
}
}
return dist, nil
}
func hammingDistWithMathBits(strOne, strTwo []byte) (dist int, err error) {
if len(strOne) != len(strTwo) {
return dist, fmt.Errorf("hamming distance can not be calculated for strings of differing length")
}
for i, _ := range strOne {
dist += bits.OnesCount8(strOne[i] ^ strTwo[i])
}
return dist, nil
}
func main() {
strOne := "this is a test"
strTwo := "wokka wokka!!!"
hDist, err := hammingDist([]byte(strOne), []byte(strTwo))
if err != nil {
log.Fatal(err)
}
fmt.Println("hamming distance:", hDist)
hDist, err = hammingDistWithMathBits([]byte(strOne), []byte(strTwo))
if err != nil {
log.Fatal(err)
}
fmt.Println("hamming distance:", hDist)
}Now we can move onto breaking a repeating-key XOR (Vigenere) encryption. We have to perform a series of steps:
- Read and decode base64 encoded file.
- Guess keysizes between 2 and 40.
- For each keysize, calculate normalized hamming distance between pairs of blocks of length keysize.
- Proceed with 2-3 keysize values that result in the smallest normalized hamming distances.
- Break ciphertext into blocks of length keysize.
- Transpose blocks by creating blocks holding the first byte of each block, etc.
- Solve each block as though it were a single character XOR.
- For each block, the single-byte XOR key that produces the best histogram is likely the correct one.
- Combine all the single-byte keys to create the full key.
package main
import (
"fmt"
"log"
"os"
"encoding/base64"
)
// keySize is a struct containing a keysize and the
// associated normalized hamming distance for the
// the average of all block pairs in the source of
// size equal to the keysize.
type keySize struct {
size int
dist float32
}
// hammingDist computes the number of differing bits in two
// byte slices as long as they are of equal length.
func hammingDist(strOne, strTwo []byte) (dist byte, err error) {
if len(strOne) != len(strTwo) {
return dist, fmt.Errorf("hamming distance can not be calculated for strings of differing length")
}
var scratch byte
for i, _ := range strOne {
scratch = strOne[i] ^ strTwo[i]
for j := 0; j < 8; j++ {
if scratch & (1 << j) > 0 {
dist++
}
}
}
return dist, nil
}
// mostProbSizes computes three key sizes between input minimum
// and maximum sizes such they are the key sizes which result
// in the smallest normalized hamming distance for each pair
// of blocks of length keysize.
func mostProbSizes(src []byte, minSize, maxSize int) (sizes [3]keySize, err error) {
for size := minSize; size <= maxSize; size++ {
// find number of pairs of blocks
// we don't really care about precisely using every byte
blockPairs := len(src) / (size*2)
if blockPairs > 128 {
blockPairs = 128
}
var sum float32
for p := 0; p < 4; p++ {
dist, err := hammingDist(src[p*(size*2):(p*(size*2))+size], src[(p*(size*2))+size:(p*(size*2))+(2*size)])
if err != nil {
return sizes, err
}
sum += float32(dist)
}
// normalize result by dividing by keysize
sum /= float32(size)
// replace in array of smallest three distances
for i, s := range sizes {
if sum < s.dist || s.dist == 0 {
sizes[i] = keySize{size: size, dist: sum}
break
}
}
}
return
}
// chuckCipherText simply splits a single slice of source
// bytes into a slice of slices of bytes such that each
// slice contains a number of bytes equal to the keysize.
// The last slice may be padded with 0's if the length
// of the source is not evenly divisible by the keysize.
func chunkCipherText(src []byte, keysize int) [][]byte {
nBlk := len(src) / keysize
if len(src) % keysize != 0 {
nBlk++
}
blocks := make([][]byte, nBlk)
for i := 0; i < nBlk-1; i++ {
blocks[i] = make([]byte, keysize)
copy(blocks[i], src[i*keysize:(i+1)*keysize])
}
// copy last block
blocks[len(blocks)-1] = make([]byte, keysize)
copy(blocks[len(blocks)-1], src[(nBlk-1)*keysize:])
return blocks
}
// transpose performs a simple transpose of a byte matrix
func transpose(blocks [][]byte) [][]byte {
// prepare transposed matrix of proper size
tr := make([][]byte, len(blocks[0]))
for r := range tr {
tr[r] = make([]byte, len(blocks))
// and populate with values
for c := range tr[r] {
copy(tr[r][c:c+1], blocks[c][r:r+1])
}
}
return tr
}
var englishCharFrequency = map[byte]float32 {
97:8.34, // a
98:1.54, // b
99:2.73, // c
100:4.14, // d
101:12.60, // e
102:2.03, // f
103:1.92, // g
104:6.11, // h
105:6.71, // i
106:0.23, // j
107:0.87, // k
108:4.24, // l
109:2.53, // m
110:6.80, // n
111:7.70, // o
112:1.66, // p
113:0.09, // q
114:5.68, // r
115:6.11, // s
116:9.37, // t
117:2.85, // u
118:1.06, // v
119:2.34, // w
120:0.20, // x
121:2.04, // y
122:0.06, // z
}
// decryptSingleCharXor iterates through each possible ascii
// character and performs a single-char XOR operation on the
// input byte slice. For each key character used, it checks if
// the output has a higher score (based on English character
// frequency) than the previous best. Finally it returns the key
// and decoded line with the highest value.
func decryptSingleCharXor(src []byte, scoringMap map[byte]float32) (key byte) {
var score float32
scratch := make([]byte, len(src))
// assume key is a single ascii character
for k := 32; k < 127; k++ {
var keyScore float32
// inverse xor with this key and sum score
copy(scratch, src)
for i := range scratch {
scratch[i] ^= byte(k)
if ((scratch[i] > 64) && (scratch[i] < 91)) {
// convert to lowercase for the purpose of scoring
keyScore += scoringMap[scratch[i]+32]
} else {
keyScore += scoringMap[scratch[i]]
}
}
// compare score with previous key
// if new score is higher, replace previous
if keyScore > score {
score = keyScore
key = byte(k)
}
}
return
}
// decryptRepeatingCharXor iterates between the bytes of key as
// performs XOR on each byte of the source.
func decryptRepeatingCharXor(src, key []byte) []byte {
dst := make([]byte, len(src))
for i := range src {
dst[i] = src[i] ^ key[i%len(key)]
}
return dst
}
func main() {
// 1. read and decode base64 encoded file
src, err := os.ReadFile("6.txt")
if err != nil {
log.Fatal(err)
}
_, err = base64.StdEncoding.Decode(src, src)
if err != nil {
log.Fatal(err)
}
// 2. guess keysizes between 2 and 40
// 3. for each keysize calculate normalized hamming distance
// 4. proceed with 3 keys with smallest normalized hamming distance
keys, err := mostProbSizes(src, 2, 40)
if err != nil {
log.Fatal(err)
}
// proceed with three best keysize candidates
for _, k := range keys {
//fmt.Printf("keysize of %v with normalized hamming distance of %v\n", k.size, k.dist)
// 5. break ciphertext into blocks of length keysize
blocks := chunkCipherText(src, k.size)
// 6. transpose blocks
tr := transpose(blocks)
// 7. solve each block as if it were a single-char XOR
key := make([]byte, len(tr))
for i, blk := range tr {
key[i] = decryptSingleCharXor(blk, englishCharFrequency)
}
// 8. combine single byte keys to create full key and test decryption
// only print the first few characters for clarity
fmt.Printf("key: %s\n", key)
fmt.Printf("decrypted text:\n%s\n\n", decryptRepeatingCharXor(src, key)[:100])
}
// we can make an educated guess based on the result from the operations above
// we see the second best key with a keysize of 29 chars resulted in text that
// was nearly English
// the key was: TER(IN$TOR X: BRIN" TH NOI6E
// testing with: Terminator x: Bring the noise
keyGuess := "Terminator X: Bring the noise"
fmt.Printf("guessed key: %v\n", keyGuess)
fmt.Printf("decrypted text:\n%s\n\n", decryptRepeatingCharXor(src, []byte(keyGuess)))
} Even when the algorithm works properly, it needs a bit of jiggering to get the proper result.
A human can quickly pick out that IMeBA&KAnd I'MR,nGI+'TH bEL)*ROckin'ONetHEemIKEeWhIL T-EFly giRLSeyEL) *iNeEcST$SYeINthe is slightly garbled text and since the key is in plain English as well, it is easy to manually test variations on TER(IN$TOR X: BRIN" TH NOI6E to find the proper key.
However, I can’t help but wonder how hard this would be to decode if (a) we didn’t know it is repeating key XOR and (b) the key is actually random.
Certainly this would be much more challenging in that case, even if this implementation of the algorithm could get you close to a proper solution.
The Base64-encoded content in this file (7.txt) has been encrypted via AES-128 in ECB mode under the key
“YELLOW SUBMARINE”.
(case-sensitive, without the quotes; exactly 16 characters; I like “YELLOW SUBMARINE” because it’s exactly 16 bytes long, and now you do too).
Decrypt it. You know the key, after all.
Easiest way: use OpenSSL::Cipher and give it AES-128-ECB as the cipher.
You can obviously decrypt this using the OpenSSL command-line tool, but we’re having you get ECB working in code for a reason. You’ll need it a lot later on, and not just for attacking ECB.
AES stands for the Advanced Encryption Standard and is a key-symmetric algorithm used by the US government. Key symmetry means that the same key is used for encryption and decryption. ECB stands for Electronic Codebook which simply means that the message is divided into blocks and encrypted separately. This is quite a simple problem then since we just have to split the source into 16-byte blocks and then decrypt each block. We can do this all in-place.
package main
import (
"fmt"
"log"
"os"
"encoding/base64"
"crypto/aes"
)
func main() {
// read and decode base64 encoded file
src, err := os.ReadFile("7.txt")
if err != nil {
log.Fatal(err)
}
_, err = base64.StdEncoding.Decode(src, src)
if err != nil {
log.Fatal(err)
}
key := "YELLOW SUBMARINE"
// pad the source to ensure it is a
// multiple of the block size
pad := len(src) % len(key)
if pad != 0 {
for i := 0; i < len(key)-pad; i++ {
src = append(src, 0)
}
}
// create AES cipher
c, err := aes.NewCipher([]byte(key))
if err != nil {
log.Fatal(err)
}
// find how many blocks
blks := len(src) / len(key)
for j := 0; j < blks; j++ {
c.Decrypt(src[j*len(key):(j+1)*len(key)],
src[j*len(key):(j+1)*len(key)])
}
fmt.Printf("%s", src)
}In this file (8.txt) are a bunch of hex-encoded ciphertexts.
One of them has been encrypted with ECB.
Detect it.
Remember that the problem with ECB is that it is stateless and deterministic; the same 16 byte plaintext block will always produce the same 16 byte ciphertext.
Since ECB will always produce the same ciphertext given the same input block, we can detect the most likely ECB-encoded text by checking if there are duplicate cipher blocks. Of course this assumes there is duplicate text in the decrypted message.
package main
import (
"fmt"
"log"
"os"
"encoding/hex"
"bufio"
"bytes"
)
func scoreLine(line []byte, blockSize int) (score int) {
nBlks := len(line)/blockSize
// normally we would care about the last block but
// in this case, the last block will already have been
// compared with all prior blocks so no need to pad
for i := 0; i < nBlks - 1; i++ {
// only need to compare with blocks ahead
for j := i + 1; j < nBlks - 1; j++ {
if bytes.Compare(
line[i*blockSize:(i+1)*blockSize],
line[j*blockSize:(j+1)*blockSize]) == 0 {
score++
}
}
// deal with last block separately
if bytes.Compare(
line[i*blockSize:(i+1)*blockSize],
line[(nBlks-2)*blockSize:]) == 0 {
score++
}
}
return
}
func main() {
file, err := os.Open("8.txt")
if err != nil {
log.Fatal(err)
}
var score int
scanner := bufio.NewScanner(file)
scanner.Split(bufio.ScanLines)
for scanner.Scan() {
decodedLine, err := hex.DecodeString(scanner.Text())
if err != nil {
log.Fatal(err)
}
if lScore := scoreLine(decodedLine, 16); lScore > score {
score = lScore
fmt.Printf("%v duplicate blocks in the following line: %v", score, decodedLine)
}
}
}A block cipher transforms a fixed-sized block (usually 8 or 16 bytes) of plaintext into ciphertext. But we almost never want to transform a single block; we encrypt irregularly-sized messages.
One way we account for irregularly-sized messages is by padding, creating a plaintext that is an even multiple of the blocksize. The most popular padding scheme is called PKCS#7.
So: pad any block to a specific block length, by appending the number of bytes of padding to the end of the block. For instance,
“YELLOW SUBMARINE”
… padded to 20 bytes would be:
“YELLOW SUBMARINE\x04\x04\x04\x04”
A block cipher works with fixed-size blocks but plaintext can almost never be divided evenly into blocks.
So we have to pad and PKCS#7 is the most popular padding method.
This method of padding appends bytes to the plaintext until it can be evenly divided into the blocksize.
The byte that it appends is equal to the number of bytes to append.
So if the blocksize is 16 and we have a plaintext of 28 bytes, we are short by 4 bytes.
We will append 4 bytes each of value 4: [4, 4, 4, 4].
We’ve already done something similar previously so this should be quite easy.
Also, fun trick in Emacs, you can press C-x = to see the ASCII or hex encoding of any character.
package main
import (
"fmt"
)
func pkcs7(src []byte, blkSize int) []byte {
// find by how much we need to pad
pad := blkSize - (len(src) % blkSize)
if pad == blkSize {
// no padding required
return src
}
// pad
padSlice := make([]byte, pad)
for i := range padSlice {
padSlice[i] = byte(pad)
}
dst := make([]byte, len(src) + pad)
copy(dst, src)
copy(dst[len(src):], padSlice)
return dst
}
func main() {
src := "YELLOW SUBMARINE"
padded := pkcs7([]byte(src), 20)
fmt.Printf("%s\n", padded)
fmt.Printf("%v\n", padded)
}CBC mode is a block cipher mode that allows us to encrypt irregularly-sized messages, despite the fact that a block cipher natively only transforms individual blocks.
In CBC mode, each ciphertext block is added to the next plaintext block before the next call to the cipher core.
The first plaintext block, which has no associated previous ciphertext block, is added to a “fake 0th ciphertext block” called the initialization vector, or IV.
Implement CBC mode by hand by taking the ECB function you wrote earlier, making it encrypt instead of decrypt (verify this by decrypting whatever you encrypt to test), and using your XOR function from the previous exercise to combine them.
The file here (10.txt) is intelligible (somewhat) when CBC decrypted against “YELLOW SUBMARINE” with an IV of all ASCII 0 (\x00\x00\x00 &c)
Do not use OpenSSL’s CBC code to do CBC mode, even to verify your results. What’s the point of even doing this stuff if you aren’t going to learn from it?
package main
import (
"fmt"
"log"
//"os"
//"encoding/base64"
"crypto/aes"
)
// ecbEncrypt performs AES ECB encryption on 16-byte blocks
// using a 16-byte key. The encryption is performed in place.
// This function assume an input that is an even multiple of
// the blocksize.
func ecbEncrypt(src, key []byte) error {
const blocksize int = 16
if len(src) % blocksize != 0 {
return fmt.Errorf("input length not a multiple of blocksize")
}
c, err := aes.NewCipher([]byte(key))
if err != nil {
return err
}
blks := len(src) / len(key)
for j := 0; j < blks; j++ {
c.Encrypt(src[j*blocksize:(j+1)*blocksize], src[j*blocksize:(j+1)*blocksize])
}
return nil
}
func main() {
k := []byte("YELLOW SUBMARINE")
src := []byte("YELLOW SUBMARINEYELLOW SUBMARINEYELLOW SUBMARINE")
err := ecbEncrypt(src, k)
if err != nil {
log.Fatal(err)
}
fmt.Println(string(src))
}