OpenCTF 2016 - Apprentice WWW (Binary 300) writeup

Solution by [Neg9] Javantea

Files:

Apprentice_www is a exploitable challenge with a simple premise.

You get to overwrite one byte. That's not enough for code execution in a normal system. But the mprotects make the whole text segment writable and executable. That's good enough get a loop around the function that overwrites bytes. Then you can overwrite the text segment with your shellcode in a special way, then your shellcode executes. Instead of writing a python script that connects and sends the integers, I chose to print the integers and paste them into netcat. Then cat /home/challenge/flag

One interesting thing that I had to overcome was the loop jump. If you overwrite the lower byte of the loop jump with your shellcode, you will jump somewhere other than the top of the loop and it'll be crash city. So instead of doing that use the fact that it's a conditional jump to have it execute your shellcode. Which value does your input have to be to get it to branch the other direction? 0. So that's why there's a

# Junk
print(0x80489db)
print(0)

at the bottom of my script. Yup.

Solution:
one_drop_andAllOFTHESUDDEN

Posted on Aug. 27, 2016, 9:30 p.m. by Javantea

OpenCTF 2016 - CGC Neophyte (Binary 300) writeup

Solution by [Neg9] Javantea

Files:

Neophyte was one of the more difficult challenges at OpenCTF that I solved. I spent 1 hour getting the first exploit to work, just a simple buffer overflow. I spent 4 or so hours getting the exploit that worked on the first binary reliable for approximately 1 in 150 binaries. The solution reads the value subtracted from EBP at address 8048546 to decide how large the buffer should be to overflow. I copied the shellcode from a teammate's solution. Then the solution reads varcmp, the byte that is compared to a changing value in the binaries. The exploit is not reliable because we don't know the address of the stack. Therefore we guess and it will crash 99.3% of the time. 0.7% of the time, it will hit the nopsled and execute our shellcode. Then you can cat /home/challenge/flag and you are done.

Details

Exploiting a buffer overflow

If you're at the point where you're having trouble exploiting this buffer overflow, you should not be so worried. You're exploiting the stack which is variable size and the stack is randomized. If the stack is enormous, you can fill it with nops and jump to where you think it might be. Stack overflows should usually be exploited in the following manner:

nopsled + shellcode + padding + address

How do we know the right amount of nopsled and padding for the address to be in the right place? The buffer size is known to you, so you can get your address executed every time. To do this dynamically, Create a pattern to crash your program. Then you can use the pattern to determine how long your buffer should be. If you don't have a pattern generator, use AAAA...BBBB. Increase the number of A's but keep just 4 B's, this makes it so you know when EIP is 0x42424242, you have the right position.

On the topic of padding, generally you want as little padding as possible, but that depends on how much data is trashed in the stack. If only 15 bytes get trashed at the end of the stack, your padding should be 15 bytes long. In this case I wasn't interested in finding out how many bytes were getting trashed on the stack, so I gave 50 bytes to padding and it worked.

Figuring out how big the buffer size is given two binaries

In neophyte you can find out the correct buffer size with one binary if you understand buffer overflows properly. But let's assume that you don't (like I didn't when I exploited this challenge) for the purpose of explanation. First you use the technique in the previous section to find out the correct length of the buffer. It doesn't matter where you measure it from, so long as you're consistent. Then you look at the values in the binary.

diff

diff -u neophyte1.jav neophyte2.jav
--- neophyte1.jav       2016-08-05 19:09:09.935916641 -0700
+++ neophyte2.jav       2016-08-05 19:39:34.523799711 -0700
@@ -163,12 +163,12 @@
 vulnerable:
  804852f: PUSH EBP
  8048530: MOV EBP, ESP ; EBP = ESP;
- 8048532: SUB ESP, 0x3db8 ; ESP -= 0x3db8;
+ 8048532: SUB ESP, 0xea8 ; ESP -= 0xea8;
  8048538: MOV EAX, [0x804a040] ; EAX = [0x804a040];
  804853d: SUB ESP, 0x4 ; ESP -= 0x4;
  8048540: PUSH EAX
- 8048541: PUSH DWORD 0x41a4
- 8048546: LEA EAX, [EBP-0x3dac]
+ 8048541: PUSH DWORD 0x129c
+ 8048546: LEA EAX, [EBP-0xea4]
  804854c: PUSH EAX
  804854d: CALL 80483d0 <fgets>
  8048552: ADD ESP, 0x10 ; ESP += 0x10;
@@ -201,8 +201,8 @@
  80485a0: ADD ESP, 0x10 ; ESP += 0x10;
  80485a3: CALL 80483c0 <getchar>
  80485a8: MOV [EBP-0x9], AL ; [EBP-0x9] = AL;
- 80485ab: CMP BYTE [EBP-0x9], 0x6b ;
- 80485af: JNZ 0x80485c8 ; if(BYTE [EBP-0x9] == 0x6b) {
+ 80485ab: CMP BYTE [EBP-0x9], 0x75 ;
+ 80485af: JNZ 0x80485c8 ; if(BYTE [EBP-0x9] == 0x75) {
  80485b1: SUB ESP, 0xc ; ESP -= 0xc;
  80485b4: PUSH DWORD 0x8048670 ; 'good gatekeeper'
  80485b9: CALL 80483f0 <puts>

There are two values that could possibly be the buffer size. One is sub esp at 8048532 and the other is sub lea at 8048546. Create the table below (the original of which I made during the competition you can find in sublea1.txt).

binary correct   subesp lea
neophyte1 15798 0x3db6 0x3db8 0x3dac
neophyte2 3758 0xeae 0xea8 0xea4

Now we do a tiny bit of algebra. The correct value - subesp is (0x3db6-0x3db8) and (0xeae-0xea8). The correct value minus sublea is (0x3db6-0x3dac) and (0xeae-0xea4). Which of the two values is consistent? sublea+4 is correct. subesp is not.

Waiting

Some hackers aren't patient enough to exploit some vulnerabilities. That's all right because you don't need to exploit every vulnerability. Some vulnerabilities you want to see patched before you have a chance to exploit it. The last step in exploiting this vulnerability is have patience and let the for loop finish the job.

bash

for i in $(seq 1 200); do echo 'new'; python3 neophyte1.py; done >gg3.txt
grep -A2 success gg3.txt |sort |uniq -c
    180 --
      4 *** Connection closed by remote host ***
      1 DontGetAngr_y___IT_WILL_GET_WORSE
    175 new
    181 resp success b'\n'
    181 shell:
Solution:
DontGetAngr_y___IT_WILL_GET_WORSE

Posted on Aug. 15, 2016, 10:50 p.m. by Javantea

Google CTF 2016 - RSACalc (crypto 300) Writeup

Hint:

Connect to ssl-added-and-removed-here.ctfcompetition.com:59999

Try our new Cloud Computing Service.

Note: Encrypt and decrypt operations expect base64-encoded input.

Connecting to the server (via SSL!) and solving a simple proof of work gives us an "RSA Calculator" that supports some basic arithmetic and Boolean operations along with encrypting and decrypting simple messages:

Usage: [operand1] operator operand2

Supported operations: +, -, , /, ^, |, &, *, sqrt, encrypt, decrypt

After 8 operations or a timeout, the system will kick you out with an encrypted copy of the flag for your troubles.

Unfortunately, messages give a different encrypted value every time they're submitted suggesting that there's some sort of random padding being applied. As you would expect the previous flag can't be decrypted on subsequent connections leading to the likely conclusion that the private key changes on every connection attempt.

There's no obvious way to even get the public key parameters, until you notice that asking for certain operations (like 2**128) gives suspiciously low results. It turns out that all operations are being performed over a modulus, and the obvious guess is that the modulus they're using is the N parameter of for their RSA encryption.

There are several ways to get N back out from this operation, but the simplest (thanks to Meta!) is to just find a number that equals zero (modulo N). The operation 1/2 gives a number that (although surprisingly large) when multiplied by 2 will be congruent to 1 (modulo N). So, because the calculator performs all the calculations modulo N we were able to verify that 1 == (1/2)*2 and 0 == ((1/2)*2)-1 == N.

Next we needed information about the padding. Requesting encryption of increasingly large plaintexts reveals that a minimum of 11 bytes of padding are mandatory (based on the 2048-bit N we discovered earlier). This is the same number of bytes as RSAES-PKCS1-v1_5 requires, which was also used in Spotted Wobbegong.

To finish discovering the public parameters we need e. Fortunately since we know N and a likely padding format we can simply encrypt a chosen plaintext locally and see if it decrypts correctly on the server. This quickly identifies 65537 as the proper value for e and confirms that PKCS v1.5 padding is indeed being used.

At this point the public portion of the key is fully discovered, but without the private key it doesn't seem possible to decrypt the flag…

But one of the more curious operations that rsacalc provides is sqrt. This allows you to reverse a quadratic residue of an arbitrary value mod N. This is easy when N is prime but computationally hard when N is a composite of two large primes…unless you happen to know and use knowledge of the component primes. In fact, it's a known equivalent to integer factorization, as described by:

The second link in particular gives you a direct recipe for calculating one particular component prime of N:

  1. Choose an element 'A' between 2…N uniformly at random and compute A=a² (mod N)
  2. Apply the square root computation technique on A, get result a′
  3. If a′=±A retry, else gcd(A-a′,N) is a non-trivial factor of N

This generally gives us one prime factor of N in two or three attempts. Once one prime is discovered you can do simple division to get the other prime, and then just implement RSA private key derivation to discover the private key, d.

From here decrypt the flag by calculating (m^d) mod N, and strip off the PKCS padding to get the flag:

CTF{What.kind.of.flower.should.never.be.put.in.a.vase-Cauliflower}

And here's the automated solver in Python:

  1 import ssl, socket, re, itertools, string, fractions, random, gmpy2
  2 from hashlib import sha1
  3 from base64 import b64encode, b64decode
  4 from Crypto.Util.number import bytes_to_long, long_to_bytes
  5 
  6 def proof_of_work(base):
  7     base = bytes(base)
  8     letters = [bytes(x) for x in string.ascii_letters]
  9 
 10     for c in itertools.combinations_with_replacement(letters, 7):
 11         work = b"".join(c)
 12         digest = sha1(base + work).hexdigest()
 13         if digest.startswith("00000"):
 14             return work
 15 
 16 e = 65537
 17 host,port = "ssl-added-and-removed-here.ctfcompetition.com",59999
 18 
 19 s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
 20 s.connect((host, port))
 21 sslSocket = socket.ssl(s)
 22 
 23 #Throw away messages until you hit the proof of work
 24 data = sslSocket.read(1024)
 25 data = sslSocket.read(1024)
 26 proof = re.findall('proof\=(.*?)\, sha1', str(data))[0]
 27 print('proof is: ' + proof)
 28 
 29 work = proof_of_work(proof)
 30 print('work is: ' + str(work))
 31 sslSocket.write(work + b'\n')
 32 
 33 data = sslSocket.read(1024)
 34 print data
 35 if(-1 != data.find('Nope')):
 36     print 'Proof of work failed.'
 37     raise
 38 
 39 #Throw away banner
 40 data = sslSocket.read(1024)
 41 data = sslSocket.read(1024)
 42 
 43 sslSocket.write('1 / 2 \n')
 44 data = sslSocket.read(1024)
 45 
 46 N = (int(data) * 2) - 1
 47 print 'N: ' + str(N)
 48 
 49 p = 0
 50 q = 0
 51 
 52 while(True):
 53     value = random.randint(2, N - 1)
 54     A = pow(value, 2, N)
 55 
 56     sslSocket.write('sqrt ' + str(A))
 57     data = sslSocket.read(1024)
 58 
 59     aPrime = int(data)
 60 
 61     if(aPrime == value or aPrime == (value + N) ):
 62         print "+- A satisfied. :( Retrying"
 63         continue
 64 
 65     if(fractions.gcd(value - aPrime, N) != 1):
 66         p = fractions.gcd(value - aPrime, N)
 67         print 'Found factor: \n' + str(p)
 68         q = N / p
 69         print 'q: \n' + str(q)
 70 
 71         if(0 == ((p * q) - N)):
 72             print '(p * q) == N! Private key found.'
 73             break
 74         else:
 75             print 'Found candidate p that did not result in N. Retrying'
 76 
 77 d = gmpy2.invert(e, (p-1)*(q-1))
 78 
 79 flag = ''
 80 
 81 while(True):
 82         sslSocket.write(b'1 + 1\n')
 83         data = sslSocket.read(1024)
 84         if data.find("flag") != -1:
 85             flag = re.findall(b'forget your flag\!\n(.*?)\n', data)[0]
 86             print(b"flag: " + flag)
 87             break
 88 
 89 flagB = bytes_to_long(b64decode(flag))
 90 
 91 decrypted = pow(flagB, d, N)
 92 decryptedB = long_to_bytes(decrypted)
 93 
 94 #Remove PKCS padding
 95 for i in range(2, len(decryptedB)):
 96     if('\0' == decryptedB[i]):
 97         print 'Decryption: ' + str(decryptedB[i:])
 98         break
 99 
100 print 'Done!'

Posted on May 4, 2016, 12:24 a.m. by reidb

Hack.lu Quals 2015 - Checkcheckcheck (crypto 150) Writeup

Hint:

We seem to have a small security problem with our new flag storage service. We already added a password login to it, with a fancy hash function, but somehow, these hackers still manage to log in. Something seems to be broken...

This challenge provided the C source code, mirrored here.

Studying the source code, it can be seen that the server does the following:

  1. Upon receiving a connection and forking, it calls the handle() method. Before any user interaction, this method reads a 32-byte password_salt and a 6-byte password_hash from disk.
  2. It loops, accepting commands from the user:
    • One command is "getflag" which checks the value of the logged_in variable to determine whether to give an error message or cat the flag file.
    • Another command is "login" followed by a password. The program does the following to process a login request:
      1. Hashes the password with the salt mentioned above. Hashing is done with SHA-256, truncated to 6 bytes.
      2. XORs the resulting hash with password_hash storing the value back into password_hash.
      3. Performs a constant-time check to see if the result of the XOR is all zero (and thus the entered password hashes to the same as the hash from disk). If so, it sets the logged_in variable to true. Otherwise, it gives an error and usefully provides us with the value of the XOR.

The main takeaways from this are that we are provided with the access of password_hash ^ hash(input_password), and that a failed login attempt overwrites password_hash with this value.

The first step is determining the desired password hash. If we attempt to login twice with the same password, the resulting XOR that is shown to us will be the initial desired password:

password_hash = desired_hash
// login attempt with "a"
password_hash = password_hash ^ hash("a") = desired_hash ^ hash("a")
// another login attempt with "a"
password_hash =  password_hash ^ hash("a") = desired_hash ^ hash("a") ^ hash("a") = desired_hash

That step is easy enough to do manually:

$ nc school.fluxfingers.net 1513
login a
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 33d5d6b96bbd
login a
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 785e64baad24
^C

So the desired password hash is 785e64baad24.

Next, we can derive what any password hashes to by XORing the resulting value of password_hash with the previous value. I wrote a script to automate this step, and gathered the hashes of all alphanumeric passwords of length one or two.

Now we need to find a subset of passwords whose hashes XORed together equals the desired hash. I tried a few unsuccessful methods until I remembered my Linear Algebra classes in college. What I was looking for was essentially a subset of the inputs that form a basis of addition in GF(2). Instead of trying to look specifically for a subset of hashes that XOR to the desired hash, look for XOR-subsets of inputs that could be combined to make any hash.

The program I wrote to finally solve this problem is:

  1 #!/usr/bin/perl
  2 
  3 use strict;
  4 use warnings;
  5 use diagnostics;
  6 use feature 'say';
  7 use Data::Dumper;
  8 
  9 my %hashes;
 10 
 11 sub numbits($)
 12 {
 13       my ($a) = @_;
 14       my $count = 0;
 15       while($a)
 16       {
 17               $count++ if($a&1);
 18               $a >>= 1;
 19       }
 20       return $count
 21 }
 22 
 23 sub remove_redundant(@)
 24 {
 25       my @values = @_;
 26       my %out_values;
 27       foreach my $value (@values)
 28       {
 29               if($out_values{$value})
 30               {
 31                       delete $out_values{$value};
 32               }
 33               else
 34               {
 35                       $out_values{$value} = 1;
 36               }
 37       }
 38       return keys %out_values;
 39 }
 40 
 41 sub reduce(@)
 42 {
 43       my @values = @_;
 44       @values = sort {$b <=> $a} @values;
 45       my @rows = map { {value=>$_, inputs=>[$_]} } @values;
 46 
 47       for my $i (0 .. $#rows - 1)
 48       {
 49               last if($rows[$i]->{value} == 0);
 50               my $i_leading0 = 48 - length(sprintf("%b", $rows[$i]->{value}));
 51               for my $j ($i + 1 .. $#rows)
 52               {
 53                       my $j_leading0 = 48 - length(sprintf("%b", $rows[$j]->{value}));
 54                       last if($j_leading0 > $i_leading0);
 55                       $rows[$j]->{value} ^= $rows[$i]->{value};
 56                       $rows[$j]->{inputs} = [ remove_redundant(@{$rows[$j]->{inputs}}, @{$rows[$i]->{inputs}}) ];
 57               }
 58               @rows = sort {
 59                       length(sprintf "%b", $b->{value}) <=> length(sprintf "%b", $a->{value}) or
 60                       index(sprintf("%b", $a->{value}), "0") <=> index(sprintf("%b", $b->{value}), "0")
 61               } @rows;
 62       }
 63       say STDERR join "\n", map { sprintf "%048b (%d)", $_->{value}, scalar(@{$_->{inputs}}) } (@rows);
 64       return @rows;
 65 }
 66 
 67 
 68 while(<>)
 69 {
 70       chomp;
 71       next unless(/^([0-9a-f]{12}) (.*)/);
 72       my ($hash, $pw) = ($1, $2);
 73       $hashes{hex($hash)} = $pw;
 74 }
 75 my @hashes_by_bits = sort {numbits($a) <=> numbits($b) } keys %hashes;
 76 my @rows = reduce(@hashes_by_bits[0 .. 99]);
 77 my $desired_hash = 0x785e64baad24;
 78 
 79 my $value = 0;
 80 my @inputs = ();
 81 while($value != $desired_hash)
 82 {
 83       printf STDERR "%012x\n%012x\n====\n", $value, $desired_hash;
 84       foreach my $row (@rows)
 85       {
 86               if(length(sprintf("%b",$desired_hash ^ $value)) == length(sprintf("%b", $row->{value})))
 87               {
 88                       $value ^= $row->{value};
 89                       @inputs = remove_redundant(@inputs, @{$row->{inputs}});
 90                       last;
 91               }
 92       }
 93 }
 94 
 95 foreach(@inputs)
 96 {
 97       say "login ".$hashes{$_};
 98       say STDERR "login ".$hashes{$_};
 99 }
100 say STDERR "getflag";
101 say "getflag";

Starting outside of the functions, lines 68 - 75 read in the password hashes retrieved earlier, stores them in $hashes, and sorts them by the number of bits set in the hash. Line 76 takes the 100 hashes (even though only 48 should be necessary) with the fewest set bits and passes that to the reduce function.

The reduce function determines the basis through a process similar to finding Row Echelon Form. Each value in @rows keeps track of a value and a list of the inputs that XOR together to make that value, initialized with the input hashes. After sorting the rows, it then enumerates through the rows from first to last, each time:

  1. XOR the current row with each of the rows below it that have the same number of leading zeros.
  2. Add this row's inputs to the lower row's inputs, removing redundant terms (any term XORed twice cancels out).
  3. Sort the rows.

To illustrate this concept on smaller inputs, the method would reduce the following random 6-bit values:

binary  decimal
001100  12
011101  29
011011  27
001000  8
110000  48
011010  26
001001  9
100001  33
101011  43
010111  23
001101  13
110101  53
100010  34
000001  1
110001  49
000101  5
001010  10
111111  63
001010  10
011001  25

into:

value  inputs
111111 (63)
010100 (43,63)
001111 (27,43,63)
000111 (43,8,63,27)
000011 (12,27,63,43)
000001 (27,12,33,63,8)
000001 (63,33,8,23)
000001 (43,8,23,53)
000001 (8,48,53,12)
000001 (48,12,63,10,8)
000000 ()
000000 (5,27,43,63,10)
000000 (10,8,25,27)
000000 (13,27,43,63,10,8)
000000 (27,12,34,63,10)
000000 (12,29,27,10)
000000 (10,63,43,27,12,9)
000000 (63,10,8,26,43,12)
000000 (49,8,10,63,12)
000000 (12,27,8,10,63,1,43)

Only the first 6 of those results are needed:

value  inputs
111111 (63)
010100 (43,63)
001111 (27,43,63)
000111 (43,8,63,27)
000011 (12,27,63,43)
000001 (27,12,33,63,8)

Any 6-bit number can be easily constructed by XORing a subset of those 6 values. And the resulting values are themselves combinations of the inputs listed in their rows.

Lines 79 - 93 then take the results of the reduce function and determines the input hashes that when XORed together results in the desired hash. It finally outputs the commands to solve the network challenge.

$ ./solve.pl hashes.remote.txt | nc school.fluxfingers.net 1513
111110000101000100000000101001010101100001000001 (1)
010000101101010100000101011001100110100001000011 (2)
001000001001011000011100110010110111100011110000 (2)
000100110100001010000001100011100000000001111100 (2)
000010111010101000111100100011100000100010101001 (2)
000001011111000000100001010010100000010010000110 (2)
000000101110110111111001001111011000000000011010 (5)
000000010101001001000010110100101010010000101101 (4)
000000001000111010100001101000110000010001010100 (6)
000000000101001110001000000001000011000100100110 (5)
000000000010011001010100110010001111110110100000 (6)
000000000001001111000110011001110100010011011001 (6)
000000000000100010000110001010100011010001100111 (9)
000000000000010111000010101110101010100110010011 (7)
000000000000001011110001111110111111110111101011 (7)
000000000000000101011000111001011100000111101101 (9)
000000000000000010000011010001111011100001010001 (6)
000000000000000001010001000000101111000011100011 (6)
000000000000000000100000100111111101000011001100 (12)
000000000000000000010000101010011101011100110100 (12)
000000000000000000001011010011000010001111010111 (10)
000000000000000000000101011100110010110001010001 (10)
000000000000000000000010011100011001111111100010 (13)
000000000000000000000001001101111100111000111110 (15)
000000000000000000000000100000100000000001011110 (12)
000000000000000000000000010100010111100110100011 (15)
000000000000000000000000001001111000101101111101 (10)
000000000000000000000000000100000000110011111101 (15)
000000000000000000000000000010100111011010101100 (17)
000000000000000000000000000001001100100000001010 (12)
000000000000000000000000000000101100111011100101 (15)
000000000000000000000000000000010110110011100100 (19)
000000000000000000000000000000001010110100000011 (12)
000000000000000000000000000000000100101110001111 (12)
000000000000000000000000000000000010001100011001 (21)
000000000000000000000000000000000001000110000100 (16)
000000000000000000000000000000000000101110111110 (20)
000000000000000000000000000000000000010110010111 (18)
000000000000000000000000000000000000001011111000 (17)
000000000000000000000000000000000000000101100111 (20)
000000000000000000000000000000000000000011111111 (23)
000000000000000000000000000000000000000001010111 (20)
000000000000000000000000000000000000000000101101 (24)
000000000000000000000000000000000000000000011111 (23)
000000000000000000000000000000000000000000001111 (20)
000000000000000000000000000000000000000000000111 (22)
000000000000000000000000000000000000000000000011 (24)
000000000000000000000000000000000000000000000001 (33)
000000000000000000000000000000000000000000000001 (26)
000000000000000000000000000000000000000000000001 (25)
000000000000000000000000000000000000000000000001 (24)
000000000000000000000000000000000000000000000001 (29)
000000000000000000000000000000000000000000000001 (25)
000000000000000000000000000000000000000000000001 (27)
000000000000000000000000000000000000000000000001 (28)
000000000000000000000000000000000000000000000001 (27)
000000000000000000000000000000000000000000000001 (29)
000000000000000000000000000000000000000000000001 (25)
000000000000000000000000000000000000000000000001 (30)
000000000000000000000000000000000000000000000001 (25)
000000000000000000000000000000000000000000000001 (24)
000000000000000000000000000000000000000000000001 (23)
000000000000000000000000000000000000000000000001 (29)
000000000000000000000000000000000000000000000001 (22)
000000000000000000000000000000000000000000000001 (28)
000000000000000000000000000000000000000000000001 (26)
000000000000000000000000000000000000000000000001 (22)
000000000000000000000000000000000000000000000001 (25)
000000000000000000000000000000000000000000000001 (23)
000000000000000000000000000000000000000000000001 (25)
000000000000000000000000000000000000000000000001 (25)
000000000000000000000000000000000000000000000001 (24)
000000000000000000000000000000000000000000000001 (32)
000000000000000000000000000000000000000000000001 (27)
000000000000000000000000000000000000000000000001 (25)
000000000000000000000000000000000000000000000001 (23)
000000000000000000000000000000000000000000000001 (27)
000000000000000000000000000000000000000000000001 (23)
000000000000000000000000000000000000000000000001 (20)
000000000000000000000000000000000000000000000001 (30)
000000000000000000000000000000000000000000000001 (24)
000000000000000000000000000000000000000000000001 (23)
000000000000000000000000000000000000000000000001 (24)
000000000000000000000000000000000000000000000001 (27)
000000000000000000000000000000000000000000000001 (23)
000000000000000000000000000000000000000000000001 (24)
000000000000000000000000000000000000000000000001 (20)
000000000000000000000000000000000000000000000001 (28)
000000000000000000000000000000000000000000000001 (27)
000000000000000000000000000000000000000000000001 (27)
000000000000000000000000000000000000000000000001 (24)
000000000000000000000000000000000000000000000001 (27)
000000000000000000000000000000000000000000000001 (27)
000000000000000000000000000000000000000000000001 (29)
000000000000000000000000000000000000000000000001 (27)
000000000000000000000000000000000000000000000001 (23)
000000000000000000000000000000000000000000000001 (22)
000000000000000000000000000000000000000000000001 (25)
000000000000000000000000000000000000000000000001 (25)
000000000000000000000000000000000000000000000000 (25)
000000000000 => 785e64baad24
42d505666843 => 785e64baad24
624319ad10b3 => 785e64baad24
7101982310cf => 785e64baad24
7aaba4ad1866 => 785e64baad24
78465d90987c => 785e64baad24
78559bf7dca5 => 785e64baad24
785d1ddde8c2 => 785e64baad24
785fec261529 => 785e64baad24
785eb4c3d4c4 => 785e64baad24
785e37846c95 => 785e64baad24
785e66869c76 => 785e64baad24
785e64f70394 => 785e64baad24
785e64a67a37 => 785e64baad24
785e64b676ca => 785e64baad24
785e64bc0066 => 785e64baad24
785e64b8c86c => 785e64baad24
785e64ba0689 => 785e64baad24
785e64baab8a => 785e64baad24
785e64baae1d => 785e64baad24
785e64baace5 => 785e64baad24
785e64baad82 => 785e64baad24
785e64baad7d => 785e64baad24
785e64baad2a => 785e64baad24
785e64baad25 => 785e64baad24
login 2W
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: c2da61799d26
login LI
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 634bf1f8b707
login Og
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 755ad1d88c94
login t1
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 0dfcb16aac84
login fi
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: a19dd8de8d84
login 33
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: b78cd3d858c4
login FZ
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 9fdcf1882861
login hz
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: ff9c7cfa1179
login Tl
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: e7caf42a1e6b
login L6
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: cddf24b81f3a
login eg
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 4dfe8c200d99
login Od
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 18ec8e4295dd
login lc
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 45ccee5371d7
login k
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 491aea7723f4
login VO
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 0b3a7ff02297
login w6
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 457ef7b4aae4
login Qq
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: e66866a622fe
login sx
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: f23930a248a6
login cf
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 6a71733050bd
login wV
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 7b694326cc14
login ZW
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: f239dba0849a
login 2T
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: 74b4df72cc1c
login IG
Whoops, that didn't work out. You probably mistyped your password, so you should try again. In case you want to debug the problem, here's the difference between the correct hash and the hash of what you entered: a7b050520c44
login dW
Login successful
getflag
Okay, sure! Let me grab that flag for you.
flag{more_MATH_than_crypto_but_thats_n0t_a_CATegory}

Posted on May 3, 2016, 11 p.m. by tecknicaltom

Defcamp CTF Quals 2015 - Custom Function Engineering (crypto 300) Writeup

Hint (with newlines added for publishing):

You are given the following ciphertext:

320b1c5900180a034c74441819004557415b0e0d1a316918011845524147384f5700264f48091e45

00110e41030d1203460b1d0752150411541b455741520544111d0000131e0159110f0c16451b0f1c

4a74120a170d460e13001e120a1106431e0c1c0a0a1017135a4e381b16530f330006411953664334

593654114e114c09532f271c490630110e0b0b

And you are also give the code used to encrypt it: encrypt.php. Show us some magic! :-)

This challenge does not have a specific flag format.

And the linked PHP script:

<?php

function xorIt($charOne, $charTwo)
{
      return $charOne ^ $charTwo;
}

function asciiValue($char)
{
      return ord($char);
}

function encrypt($plainText)
{
      $length = strlen($plainText);
      $space = 0xA;
      $cipherText = "";

      for ($i = 0; $i < $length; $i++) {
              if ($i + $space < $length - 1) {
                      $cipherText .= xorIt($plainText[$i], $plainText[$i + $space]);
              } else {
                      $cipherText .= xorIt($plainText[$i], $plainText[$space]);
              }

              $space = (asciiValue($plainText[$i]) % 2 == 0 ? $space + 1 : $space - 1);
      }

      return bin2hex($cipherText);
}

?>

I fought with this one off and on throughout most of the weekend, attempting to break it through cryptanalysis. It was obvious that the encryption was far from secure. The bytes of the ciphertext are just a XOR of two plaintext bytes each. It's obvious which plaintext bytes go into the first ciphertext byte, but after that, it's less obvious. It also gets a bit screwy near the end of the plaintext. Like many of the other teams' writeups that I've seen, I attempted a tree-based approach, trying to determine possible values for the progression of the space variable, but it seemed to take forever and branch into an unwieldy number of possibilities. Personally, during the rush of a CTF isn't when I do my best cryptanalysis.

So eventually on the final day of the CTF, I thought this might actually be a good exercise for a SMT solver. So I threw together the following solver with Z3py. I had to play a lot with the assumptions made about the unknowns: over-constrained and the problem was unsat, under-constrained and I got a garbage plaintext that may encrypt to the given ciphertext but which doesn't get me any points. Below is a commented version of the solver script:

#!/usr/bin/python

from z3 import *

ciphertext = [ 0x32, 0x0b, 0x1c, 0x59, 0x00, 0x18, 0x0a, 0x03, 0x4c, 0x74, 0x44, 0x18, 0x19, 0x00, 0x45, 0x57, 0x41, 0x5b, 0x0e, 0x0d, 0x1a, 0x31, 0x69, 0x18, 0x01, 0x18, 0x45, 0x52, 0x41, 0x47, 0x38, 0x4f, 0x57, 0x00, 0x26, 0x4f, 0x48, 0x09, 0x1e, 0x45, 0x00, 0x11, 0x0e, 0x41, 0x03, 0x0d, 0x12, 0x03, 0x46, 0x0b, 0x1d, 0x07, 0x52, 0x15, 0x04, 0x11, 0x54, 0x1b, 0x45, 0x57, 0x41, 0x52, 0x05, 0x44, 0x11, 0x1d, 0x00, 0x00, 0x13, 0x1e, 0x01, 0x59, 0x11, 0x0f, 0x0c, 0x16, 0x45, 0x1b, 0x0f, 0x1c, 0x4a, 0x74, 0x12, 0x0a, 0x17, 0x0d, 0x46, 0x0e, 0x13, 0x00, 0x1e, 0x12, 0x0a, 0x11, 0x06, 0x43, 0x1e, 0x0c, 0x1c, 0x0a, 0x0a, 0x10, 0x17, 0x13, 0x5a, 0x4e, 0x38, 0x1b, 0x16, 0x53, 0x0f, 0x33, 0x00, 0x06, 0x41, 0x19, 0x53, 0x66, 0x43, 0x34, 0x59, 0x36, 0x54, 0x11, 0x4e, 0x11, 0x4c, 0x09, 0x53, 0x2f, 0x27, 0x1c, 0x49, 0x06, 0x30, 0x11, 0x0e, 0x0b, 0x0b ]

length = len(ciphertext)
decrypt_len = length
plaintext = [ BitVec('p_%d'%i, 8) for i in range(0, length) ]
spaces = [ Int('sp_%d'%i) for i in range(0, length) ]

# the "space" value starts at 10, assume it doesn't deviate by more than 20
space_deviation = 20
min_space = 10-space_deviation
max_space = 10+space_deviation

s = Solver()
s.add(spaces[0] == 0xA)
for i in range(0, decrypt_len):

    # make some assumptions about the contents of the plaintext. otherwise, the solution it finds
    # is garbage that encrypts to the given ciphertext, but doesn't give me a flag
    s.add(Or(
        # plaintext is a symbol between space (0x20) and slash (0x2f)
        And(UGE(plaintext[i], ord(' ')), ULE(plaintext[i], ord('/'))),
        # plaintext is one of those symbols often in flags
        plaintext[i] == ord('{'),
        plaintext[i] == ord('}'),
        plaintext[i] == ord('_'),
        # plaintext is alphanumeric
        And(UGE(plaintext[i], ord('A')), ULE(plaintext[i], ord('Z'))),
        And(UGE(plaintext[i], ord('a')), ULE(plaintext[i], ord('z'))),
        And(UGE(plaintext[i], ord('0')), ULE(plaintext[i], ord('9')))
        ))

    # add assertions about what the next value of "space" will be, based on the current value
    # of "space" and the current plaintext
    if i != length-1:
        s.add(If(plaintext[i] & 1 == 0, spaces[i+1]==spaces[i]+1, spaces[i+1]==spaces[i]-1))

    # add assertions about our assumptions for the range of "space"
    s.add(spaces[i] <= max_space)
    s.add(spaces[i] >= min_space)

    # finally add assertion that we get the given ciphertext character based on the space value and
    # the unknown plaintext
    for sp in range(min_space, max_space+1):
        if(i + sp < length - 1):
            s.add(Implies(spaces[i] == sp, ciphertext[i] == plaintext[i] ^ plaintext[(i+sp+length)%length]))
        else:
            s.add(Implies(spaces[i] == sp, ciphertext[i] == plaintext[i] ^ plaintext[(sp+length)%length]))


print "Attempting to solve..."
print s.check()
m=s.model()

# print out the plaintext
print ''.join([chr(m[plaintext[i]].as_long()) for i in range(length)])

The script runs for about 2.5 minutes, and produces the following output:

Attempting to solve...
sat
Very well done you CTF pwner. Now I have to give you the reward for all this hard work or maybe guessing. The flag is cryptanalysis_is_hard

Posted on Oct. 14, 2015, 3:18 p.m. by tecknicaltom