Solving The Cryptopals Crypto Challenges (Set 1 - Challenge 3-5)
Overview
I came across the cryptopals crypto challenges in this blog (A really cool blog, I recommend following it). The challenges looked interesting and I am solving them.
- I am writing this blog series to record and analyse my process of solving a problem.
- All published parts of the series can be found here.
- All code in this series can be found here.
- All solutions are in Golang.
- As the intention of this exercise is to maximise learning, I will be doing it the old-fashioned way, sans LLMs.
- I welcome all feedback and critique on any part of the blog series.
Challenge 3
Problem
There is an input string on which a single character has been xored against. We will have to find the key and decrypt the message. The challenge also asks to find some a way to identify a successful decryption automatically.
Solutioning
Right off the bat, I am making some assumptions. I’m assuming that a character that was used to encrypt refers to a letter or a number. I’m also splitting the problem into two:
- Trying out all the characters one by one and decrypting it. I will then verify it manually.
- Find a way to verify if a successful decryption has happened automatically.
Bruteforcing the Decryption
I’m using existing functions and sending it a list of all the characters one by one. The characters are put in an array of the same length as the input, to make it work with the existing functions.
// One character has been xored against a given string.
// Have to find out what that character is
package main
import (
"encoding/hex"
"fmt"
)
func decodeHex(ip string) []byte {
op := make([]byte, hex.DecodedLen(len(ip)))
_, err := hex.Decode(op, []byte(ip))
if err != nil {
fmt.Print(err)
}
return op
}
func xor(op1 []byte, op2 []byte) []byte {
op := make([]byte, len(op1))
for i := 0; i < len(op1); i++ {
op[i] = op1[i] ^ op2[i]
}
return op
}
func main() {
allCharacters := "abcdefghijklmnopqrstuvwxyz1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"
inp1 := "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736"
hex1 := decodeHex(inp1)
hex2 := make([]byte, len(hex1))
for i := 0; i < len(allCharacters); i++ {
for j := 0; j < len(hex1); j++ {
hex2[j] = allCharacters[i]
}
res := xor(hex1, hex2)
fmt.Print(string(allCharacters[i]), " : ", string(res), "\n")
}
}
Verification of Successful Decryption
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.
This was the hint given to us figure out the solution. One thing I noticed from bruteforcing earlier was that the incorrect solutions contained a lot of non-alphanumeric characters. So, we can find the ratio of alphabets to non-alphabets and the one with the highest alphabet to non-alphabet ratio would be the answer.
Implementing that with some revisions led me to the final answer:
// One character has been xored against a given string.
// Have to find out what that character is
package main
import (
"encoding/hex"
"fmt"
"unicode"
)
func decodeHex(ip string) []byte {
op := make([]byte, hex.DecodedLen(len(ip)))
_, err := hex.Decode(op, []byte(ip))
if err != nil {
fmt.Print(err)
}
return op
}
func xor(op1 []byte, op2 []byte) []byte {
op := make([]byte, len(op1))
for i := 0; i < len(op1); i++ {
op[i] = op1[i] ^ op2[i]
}
return op
}
func legitAnswerProbability(inp string) float64 {
score := 0.0
symbol := 0
alphanum := 0
for _, c := range inp {
if unicode.IsLetter(c) {
alphanum += 1
} else {
symbol += 1
}
}
score = float64(alphanum) / float64(symbol)
return score
}
func main() {
allCharacters := "abcdefghijklmnopqrstuvwxyz1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"
inp1 := "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736"
hex1 := decodeHex(inp1)
hex2 := make([]byte, len(hex1))
highest_ratio := 0.0
var legitAnswer, key string
for i := 0; i < len(allCharacters); i++ {
for j := 0; j < len(hex1); j++ {
hex2[j] = allCharacters[i]
}
res := xor(hex1, hex2)
stringRatio := legitAnswerProbability(string(res))
if highest_ratio <= stringRatio {
highest_ratio = stringRatio
legitAnswer = string(res)
key = string(allCharacters[i])
}
}
fmt.Print(key, " : ", legitAnswer, " entropy:", highest_ratio, "\n")
}
Challenge 4
Problem
We are given a list of 300+ strings of 60 characters each, one of which has been encrypted by a single character using XOR. We are to find which is the encrypted string. Link, just because.
Solutioning
We already have code to decrypt a given string. We can use the legit-ness score we developed earlier and apply to each decrypted output we get, whichever has the highest legitness score would be the encrypted string.
// One character has been xored against one of the given strings.
// Have to find out what that string is
package main
import (
"encoding/hex"
"fmt"
"strings"
"unicode"
)
func decodeHex(ip string) []byte {
op := make([]byte, hex.DecodedLen(len(ip)))
_, err := hex.Decode(op, []byte(ip))
if err != nil {
fmt.Print(err)
}
return op
}
func xor(op1 []byte, op2 []byte) []byte {
op := make([]byte, len(op1))
for i := 0; i < len(op1); i++ {
op[i] = op1[i] ^ op2[i]
}
return op
}
func legitAnswerProbability(inp string) float64 {
score := 0.0
symbol := 0
alphanum := 0
for _, c := range inp {
if unicode.IsLetter(c) || unicode.IsSpace(c) {
alphanum += 1
} else {
symbol += 1
}
}
score = float64(alphanum) / float64(symbol)
return score
}
func decryptOneString(inp string) (string, string, float64) {
allCharacters := "abcdefghijklmnopqrstuvwxyz1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"
hex1 := decodeHex(inp)
hex2 := make([]byte, len(hex1))
highest_ratio := 0.0
var legitAnswer, key string
for i := 0; i < len(allCharacters); i++ {
for j := 0; j < len(hex1); j++ {
hex2[j] = allCharacters[i]
}
res := xor(hex1, hex2)
stringRatio := legitAnswerProbability(string(res))
if highest_ratio <= stringRatio {
highest_ratio = stringRatio
legitAnswer = string(res)
key = string(allCharacters[i])
}
}
// fmt.Print(key, " : ", legitAnswer, " entropy:", highest_ratio, "\n")
return key, legitAnswer, highest_ratio
}
func main() {
// Sample input for brevity
input := `0e3647e8592d35514a081243582536ed3de6734059001e3f535ce6271032
32042f46431d2c44607934ed180c1028136a5f2b26092e3b2c4e2930585a`
highest_ratio := 0.0
var legitAnswer, encryptionKey, inputString string
lines := strings.Split(input, "\n")
for _, line := range lines {
key, decryptedString, ratio := decryptOneString(line)
if ratio >= highest_ratio {
highest_ratio = ratio
legitAnswer = decryptedString
encryptionKey = key
inputString = line
}
}
fmt.Print(inputString, " ", encryptionKey, " ", legitAnswer, " ", highest_ratio, "\n")
}
I was thinking of parallelising if I noticed any slowness, but it was almost instant for the entire input, so I didn’t bother with it.
Challenge 5
Problem
We are supposed to implement Repeating Key XOR.
If we have a key of length 3 ICE, and a string of length 7, BURNING. We are supposed to encrypt it in the following way.
| Input Character | Key Character | Input Index | Key Index | Operation |
|---|---|---|---|
| B | I | 0 | 0 | B ^ I |
| U | C | 1 | 1 | U ^ C |
| R | E | 2 | 2 | R ^ E |
| N | I | 3 | 0 | N ^ I |
| I | C | 4 | 1 | I ^ C |
| N | E | 5 | 2 | N ^ E |
| G | I | 6 | 0 | G ^ I |
In practice, it will not be character, it will be bytes. Here is the challenge link.
Solutioning
This is also pretty straightforward. XOR is something we have aleady done. The only new thing is to figure out how to map each input character to output character. Based on the above table, you see that the index of the key cycles from 0 to 3. We can implement this in code by doing a modulo operation. In the above example, it would be as follows:
| Input Index | Key Index | Input Index % Key Length | Resulting Index |
|---|---|---|
| 0 | 0 | 0 % 3 | 0 |
| 1 | 1 | 1 % 3 | 1 |
| 2 | 2 | 2 % 3 | 2 |
| 3 | 0 | 3 % 3 | 0 |
| 4 | 1 | 4 % 3 | 1 |
| 5 | 2 | 5 % 3 | 2 |
| 6 | 0 | 6 % 3 | 0 |
Once we put all this together, we have the following code, which is the solution:
// Implement repeating key XOR
package main
import (
"encoding/hex"
"fmt"
)
func encodeToHex(ip string) []byte {
op := make([]byte, hex.EncodedLen(len(ip)))
hex.Encode(op, []byte(ip))
return op
}
func repeatingKeyXor(plaintext []byte, key []byte) []byte {
op := make([]byte, len(plaintext))
for i := 0; i < len(plaintext); i++ {
op[i] = plaintext[i] ^ key[i%len(key)]
}
fmt.Print(len(op))
return op
}
func main() {
input := `Burning 'em, if you ain't quick and nimble
I go crazy when I hear a cymbal`
key := "ICE"
ciphertext := repeatingKeyXor([]byte(input), []byte(key))
fmt.Print(input, "=> ", string(encodeToHex(string(ciphertext))))
}
Conclusion
The next challenge is about breaking the repeating key XOR. It looks more challenging than the previous ones. So, stay tuned.