## part 1
Part 1 requires to decrypt the cipher to obtain the location of the assignment specification. The cipher consists of 16 lines, which are XORed with the same secret key. The idea is make good use of the knowledege of linguistic statistics of English.
If two ciphers are XORed from the same key, then we may be able to eliminate the secret key by XORing this two ciphers, i.e.,
$$cipher_1 = plain_1\oplus key$$
$$cipher_2 = plain_2\oplus key$$
then:
$$cipher_1\oplus cipher_2 = plain_1\oplus plain_2$$
We all know English consists of alphabet and punctuation, so I enumerate how 26 upper case characters XORed with while space (‘ ‘) will return, and I get:
0x61 ‘A’^’ ‘
0x62 ‘B’^’ ‘
0x63 ‘C’^’ ‘
:
0x79 ‘Y’^’ ‘
0x7a ‘Z’^’ ‘
Which means that if I get such character (0x61-0x7a), then it is possible that two plaintexts are 1 uppercase character with 1 white space. And I found such pair of plains is first line and last line.
I guess the first character of the key is 0x6b from above process, then I recover the all line’s first character and found two ‘T’s (line 8 and 12) follows by 3 common letters, which means that they are probably ‘The ‘, ‘This’, ‘That’, ‘They’, such common patterns. I tried out all of them and found that ‘The ‘ is the correct plaintext.
Then the 2nd plain becomes ‘Info’, I guess it should be ‘Information’, so to recover the next key. Follow such process, I successfully obtained the necessary key (length 73) to decrypt the location of assignment3. Actually, the plain text is (the last line):
> The assignment is in https://cs.adelaide.edu.au/~yval/SP18/A3ishere/assignment3/pdf
## Part 2
### Description of the test environment
I use american fuzzy lop tool to do the fuzzing.
I use the big-num 4 solution of assingment 2.
I write `main.c` which reads two numbers from standard input and do computation with big-num 4 solution and the ybn library respectively. Convert the result to string and compare whether they are equal. If not, call `abort` function.
I write the `makefile` to compile the ground truth, ybn library and the main.c with `afl-clang `.
“`shell
all: main lib ylib
lib: bn.c
# gcc -c bn.c -o bignum.o -Wall -std=c99
~/afl/afl-2.52b/afl-clang -c bn.c -o bignum.o -Wall -std=c99
ar -rcs libbn.a bignum.o
ylib: ybn.c
# gcc -c ybn.c -o ybignum.o -Wall -std=c99
~/afl/afl-2.52b/afl-clang -c ybn.c -o ybignum.o -Wall -std=c99
ar -rcs libybn.a ybignum.o
# ~/afl/afl-2.52b/afl-clang main.c -L . -lbn -o calc -Wall
main: main.c lib ylib
# gcc main.c -L . -lbn -lybn -o calc -Wall -std=c99
~/afl/afl-2.52b/afl-clang main.c -L . -lbn -lybn -o calc -Wall -std=c99
# gcc main.c bn.c ybn.c -o calc -Wall -std=c99
“`
The `test_cases` directory contains the test input files used for fuzzing.
The following command is used to start the fuzzing test.
“`
~/afl/afl-2.52b/afl-clang -i ./test_cases/ -o find ./calc
“`
During the process, I invoked above commands multiple times with diffrent `find` directories. Thus, there are multiple directory whose names starting with `find`. These directories contains the crash input found.
#### Fuzzing process
My strategy is to test functions one by one. Starting with `ybn_fromString` and `ybn_toString` functions. Do the fuzzing testing, find the input that cause the crash. Modify the code, do fuzzing testing again. Until there are no more crashes.
Then I modify the main.c to test the next functions. Recompile and repeat the fuzzing process. In this way, I find the bugs one by one.
### Bugs Found
#### Bug `ybn_fromString`
##### test case revealing problem
“`
99281 3
“`
The ybn read 99281 as 33745
##### Problem
“`c
if (factor == 100000) {
ybn_muladd(bn, factor, digit);
factor = 1;
digit = 0;
}
“`
The condition is wrong. Because max value of uint16_t is 65536 – 1. Thus factor must less than 65536 – 1 to this.
##### Fix
change 100000 to 10000
“`
if (factor == 10000) {
ybn_muladd(bn, factor, digit);
factor = 1;
digit = 0;
}
“`
#### Bug `ybn_add`
##### test case revealing problem
“`
-1 2
“`
bn : 1
ybn: -3
##### Problem
“`c
int ybn_add(ybn_t result, ybn_t a, ybn_t b) {
int rv;
#ifdef UNDERGRAD
rv = ybn_addmagnitude(result, a, b);
#else
if (a->ybn_sign == b->ybn_sign)
rv = ybn_addmagnitude(result, a, b);
else
rv = ybn_submagnitude(result, a, b);
#endif
if (rv == -1)
return -1;
result->ybn_sign *= a->ybn_sign;
return 0;
}
“`
It just add the magnitude and don’t consider the sign of a, b.
##### Fix
If the sign of a and b are the same, then use addmagnitude. Otherwise subtract value with small magnitude from value with larger magnitude. Thus, I add a function to compare the magnitude of big number.
“`C
static int compare(ybn_t a, ybn_t b)
{
if(a->ybn_len < b->ybn_len )
{
return -1;
}
if(a->ybn_len > b->ybn_len )
{
return 1;
}
int n = a->ybn_len;
for(int i=n – 1; i >= 0; i–)
{
printf(“digit %d: %d %d\n”,i, a->ybn_data[i], b->ybn_data[i] );
if(a->ybn_data[i] < b->ybn_data[i])
{
return -1;
}
if(a->ybn_data[i] > b->ybn_data[i])
{
return 1;
}
}
return 1;
}
int ybn_add(ybn_t result, ybn_t a, ybn_t b) {
int rv;
#ifdef UNDERGRAD
if (a->ybn_sign == b->ybn_sign){
rv = ybn_addmagnitude(result, a, b);
}
else {
int sign = compare(a, b);
if(sign > 0)
{
rv = ybn_submagnitude(result, a, b);
}else{
rv = ybn_submagnitude(result, b, a);
}
result->ybn_sign = sign;
}
#else
if (a->ybn_sign == b->ybn_sign)
rv = ybn_addmagnitude(result, a, b);
else
rv = ybn_submagnitude(result, a, b);
#endif
if (rv == -1)
return -1;
result->ybn_sign *= a->ybn_sign;
return 0;
}
“`
#### Bug `ybn_sub`
##### test case revealing problem
“`
-1 2
“`
sub not equal
bn : -3
ybn: 0
##### Problem
“`c
int ybn_sub(ybn_t result, ybn_t a, ybn_t b) {
int rv;
#ifdef UNDERGRAD
rv = ybn_submagnitude(result, a, b);
#else
if (a->ybn_sign == b->ybn_sign)
rv = ybn_submagnitude(result, a, b);
else
rv = ybn_addmagnitude(result, a, b);
#endif
if (rv == -1)
return -1;
#ifdef UNDERGRAD
if (result->ybn_sign < 0) {
result->ybn_len = 0;
result->ybn_sign = 1;
}
#endif
result->ybn_sign *= a->ybn_sign;
return 0;
}
“`
Similar with problem in ybn_add, It just sub the magnitude and don’t consider the sign of a, b.
##### Fix
If the sign of a and b are the same, then use ybn_submagnitude and subtract value with small magnitude from value with larger magnitude. Otherwise use ybn_submagnitude. Adjust the sign properly in the end.
“`C
int ybn_sub(ybn_t result, ybn_t a, ybn_t b) {
int rv;
#ifdef UNDERGRAD
rv = ybn_submagnitude(result, a, b);
if (a->ybn_sign == b->ybn_sign){
int sign = compare(a, b);
if(sign > 0)
{
rv = ybn_submagnitude(result, a, b);
}else{
rv = ybn_submagnitude(result, b, a);
}
result->ybn_sign = sign;
}
else {
rv = ybn_addmagnitude(result, a, b);
}
#else
if (a->ybn_sign == b->ybn_sign)
rv = ybn_submagnitude(result, a, b);
else
rv = ybn_addmagnitude(result, a, b);
#endif
if (rv == -1)
return -1;
result->ybn_sign *= a->ybn_sign;
return 0;
}
“`