Crypto Attacker Burp Plugin

I recently wrote a burp plugin for common crypto attacks in web apps. Check out the code on github (I also submitted to BApp store a couple days ago). I hope to add more modules as time goes on, but to start with, here is what it has:

  • Active Scanning to detect padding Oracle attacks
  • Active Scanning capabilities to detect input being encrypted with ECB and reflected back (can be slow)
  • Attack tab to encrypt/decrypt padding oracles
  • Attack tab to decrypt ECB where you control part of the request

Here are some slides about it, and giving some background on the attacks it’s doing:

And some screenshots of it in action:

Scan

config

Decrypt

EncryptPNG

I hope this is useful to some of you!

Free Stanford ‘Intro to Cryptography’ Class Review

Last Spring I took my first coursera class, Introduction to Cryptogaphy taught by Dan Boneh. In college I took a few crypto classes, and I also deal with some crypto problems at work and in CTF. Although I’m definitely not a crypto expert, I had a pretty good background going into the class. Looking at the syllabus, I expected to work through a few interesting problems, but I didn’t expect to get too much out of it.

The class certainly exceeded my expectations. Here are the obvious things: Dan knows crypto backward and forward, and is a great teacher. The format was great – I liked being able to rewind videos at pieces I didn’t understand at first. The forum was also great – other students would answer my questions (I answered a few for other people also), and Dan himself would regularly chime in with answers to tricky problems people ran into.

One of the biggest reasons I think the class was so good was its focus on offense. I don’t really understand how defensive security people can try to defend stuff without understanding offense… yet the crypto classes I’d taken before tried to do exactly that. How was I supposed to understand why things needed to be done a certain way if I don’t know how it can break? Crypto books have been the same way – every crypto book I’ve read before (e.g. Bruce Schneier books) don’t seem to give much page space to offense. Dan brings the attacker’s perspective into every lecture, and I have a much better understanding of practical cryptography because of it.

I did manage to finish the class, but it was a lot more difficult than I expected (a good difficult :)) They seem to offer this class regularly, and I couldn’t recommend it more to anyone interested in cryptography.

accomplishment

Here are excerpts of my favorite problems he gave us to solve, and my solution for those problems. If you’re planning on taking the full class – spoiler alert. These questions might also be interesting if you don’t want to take an entire class, but just want to try and solve some super cool crypto problems. One note is all of these problems were optional, which was a decision made early on because he didn’t want programming to be a prerequisite. These problems are not required to get a coveted statement of accomplishment.

Week 1 – Two Time Pad (Reusing Stream Cipher Keys)

Problem:

“Let us see what goes wrong when a stream cipher key is used more than once. Below are eleven hex-encoded ciphertexts that are the result of encrypting eleven plaintexts with a stream cipher, all with the same stream cipher key. Your goal is to decrypt the last ciphertext, and submit the secret message within it as solution. ” These ciphertexts are (sorry for the poor formatting, but you should be able to copy them out):

ciphers = [
"315c4eeaa8b5f8aaf9174145bf43e1784b8fa00dc71d885a804e5ee9fa40b16349c146fb778cdf2d3aff021dfff5b403b510d0d0455468aeb98622b137dae857553ccd8883a7bc37520e06e515d22c954eba5025b8cc57ee59418ce7dc6bc41556bdb36bbca3e8774301fbcaa3b83b220809560987815f65286764703de0f3d524400a19b159610b11ef3e",
"234c02ecbbfbafa3ed18510abd11fa724fcda2018a1a8342cf064bbde548b12b07df44ba7191d9606ef4081ffde5ad46a5069d9f7f543bedb9c861bf29c7e205132eda9382b0bc2c5c4b45f919cf3a9f1cb74151f6d551f4480c82b2cb24cc5b028aa76eb7b4ab24171ab3cdadb8356f",
"32510ba9a7b2bba9b8005d43a304b5714cc0bb0c8a34884dd91304b8ad40b62b07df44ba6e9d8a2368e51d04e0e7b207b70b9b8261112bacb6c866a232dfe257527dc29398f5f3251a0d47e503c66e935de81230b59b7afb5f41afa8d661cb",
"32510ba9aab2a8a4fd06414fb517b5605cc0aa0dc91a8908c2064ba8ad5ea06a029056f47a8ad3306ef5021eafe1ac01a81197847a5c68a1b78769a37bc8f4575432c198ccb4ef63590256e305cd3a9544ee4160ead45aef520489e7da7d835402bca670bda8eb775200b8dabbba246b130f040d8ec6447e2c767f3d30ed81ea2e4c1404e1315a1010e7229be6636aaa",
"3f561ba9adb4b6ebec54424ba317b564418fac0dd35f8c08d31a1fe9e24fe56808c213f17c81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e9582f5ef375f0a4ae20ed86e935de81230b59b73fb4302cd95d770c65b40aaa065f2a5e33a5a0bb5dcaba43722130f042f8ec85b7c2070",
"32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30ee714979c7e1123a8bd9822a33ecaf512472e8e8f8db3f9635c1949e640c621854eba0d79eccf52ff111284b4cc61d11902aebc66f2b2e436434eacc0aba938220b084800c2ca4e693522643573b2c4ce35050b0cf774201f0fe52ac9f26d71b6cf61a711cc229f77ace7aa88a2f19983122b11be87a59c355d25f8e4",
"32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd90f1fa6ea5ba47b01c909ba7696cf606ef40c04afe1ac0aa8148dd066592ded9f8774b529c7ea125d298e8883f5e9305f4b44f915cb2bd05af51373fd9b4af511039fa2d96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d9681596934777e2275b381ce2e40582afe67650b13e72287ff2270abcf73bb028932836fbdecfecee0a3b894473c1bbeb6b4913a536ce4f9b13f1efff71ea313c8661dd9a4ce",
"315c4eeaa8b5f8bffd11155ea506b56041c6a00c8a08854dd21a4bbde54ce56801d943ba708b8a3574f40c00fff9e00fa1439fd0654327a3bfc860b92f89ee04132ecb9298f5fd2d5e4b45e40ecc3b9d59e9417df7c95bba410e9aa2ca24c5474da2f276baa3ac325918b2daada43d6712150441c2e04f6565517f317da9d3",
"271946f9bbb2aeadec111841a81abc300ecaa01bd8069d5cc91005e9fe4aad6e04d513e96d99de2569bc5e50eeeca709b50a8a987f4264edb6896fb537d0a716132ddc938fb0f836480e06ed0fcd6e9759f40462f9cf57f4564186a2c1778f1543efa270bda5e933421cbe88a4a52222190f471e9bd15f652b653b7071aec59a2705081ffe72651d08f822c9ed6d76e48b63ab15d0208573a7eef027",
"466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31c9941cf110abbf409ed39598005b3399ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbf3575c3b8edc9ba7f537530541ab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83",
"32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904"
]

Solution

The most important piece of this is to realize that XORing the ciphertexts together produces the xor of the plaintexts. Additionally, if you can guess at the next character for a given row, you can xor the ciphertext with what it should be to produce the key.

For example, if the ciphertext were 89 and the letter should be ‘e’, then

>>> hex(ord('e') ^ 0x89)

would equal the key. You can apply this key to all rows and when you get it wrong, everything looks wonky.

So to demonstrate, the first step is to get a foothold. I postulated 32510b was “the” because it was repeated several times at the beginning and ‘the’ is the most common trigram. Applying this as a key, everything looked correct (try another common one, like ‘and’, and it will look off). I went one key at a time from there, using the following program.

#!/usr/bin/python

import sys
from optparse import OptionParser


#ciphers = ... #found above

class twotimepad:
    
    def __init__(self):
        #based on what we know so far...
        self.keysofar = [0x46, 0x39, 0x6e]



    def get_freq(self, charArray):
        letterdict = {}
        for i in charArray:
            try:
                letterdict[i] += 1
            except KeyError:
                letterdict = 1
        return letterdict

    def print_mSoFar(self):
        c_sofar = [i[0:len(self.keysofar)*2] for i in ciphers]
        for i in range(0,11):
            sys.stdout.write(str(i) + ".\t")
            for j in range(0, len(self.keysofar)):
                a = self.keysofar[j];
                b = int(c_sofar[i][j*2:j*2+2], 16)
                sys.stdout.write(chr(self.keysofar[j] ^ int(c_sofar[i][j*2:j*2+2], 16)))
            print ""

    def getnextchar(self, i):        
        nextchar = ciphers[i]
        nextchar = nextchar[len(self.keysofar)*2:len(self.keysofar)*2+2]       
        return nextchar
        
    def print_next_letter(self):
        for i in range(0,11):
            print (str(i) + ":\t"+ self.getnextchar(i))

    def add_key(self, num, letter='a'):
        if num == -1:
            self.keysofar = self.keysofar[:-1]
        else:
            self.keysofar.append(ord(letter) ^ int(self.getnextchar(num), 16))
            
    def run(self):        
        while 1:
            print "Current KEY"
            print self.keysofar
            print ("\r\nStuff so Far")
            self.print_mSoFar()
            print "\r\nNext Letter"
            #self.print_next_letter()
            num = int(raw_input("\r\n\r\nEnter next number (-1 for mistake): "))
            letter = raw_input("Enter letter: ")
            self.add_key(num, letter)
    
m = twotimepad()
m.run()

This makes a program where you get a shell thing to eyeball one character at a time.

1a

The final key was the following:

Key = [70, 57, 110, 137, 201, 219, 216, 204, 152, 116, 53, 42, 205, 99, 149, 16, 46, 175, 206, 120, 170, 127, 237, 40, 160, 127, 107, 201, 141, 41, 197, 11, 105, 176, 51, 154, 25, 248, 170, 64, 26, 156, 109, 112, 143, 128, 192, 102, 199, 99, 254, 240, 18, 49, 72, 205, 216, 232, 2, 208, 91, 169, 135, 119, 51, 93, 174, 252, 236, 213, 156, 67, 58, 107, 38, 139, 96, 191, 78, 240, 60, 154, 97]

And the final secret message was:

the secret message is: When using a stream cipher, never use the key more than once

Week 1 – Breaking a Linear Congruential Generator

Problem:

The PRG described below uses a 56-bit secret seed. Running the program generates the following first nine outputs of the PRG:

output #1: 210205973
output #2: 22795300
output #3: 58776750
output #4: 121262470
output #5: 264731963
output #6: 140842553
output #7: 242590528
output #8: 195244728
output #9: 86752752

Show that this PRG is insecure by computing the next output. What is the next output (output #10) of the PRG? Note that you are not given the seed.

import random

P = 295075153L   # about 2^28

class WeakPrng(object):
    def __init__(self, p):   # generate seed with 56 bits of entropy
        self.p = p
        self.x = random.randint(0, p)
        self.y = random.randint(0, p)
   
    def next(self):
        # x_{i+1} = 2*x_{i}+5  (mod p)
        self.x = (2*self.x + 5) % self.p

        # y_{i+1} = 3*y_{i}+7 (mod p)
        self.y = (3*self.y + 7) % self.p

        # z_{i+1} = x_{i+1} xor y_{i+1}
        return (self.x ^ self.y) 


prng = WeakPrng(P)
for i in range(1, 10):
  print "output #%d: %d" % (i, prng.next())

Solution

This looks like a Linear Congruential generator. from wikipedia: The period of a general LCG is at most m, and for some choices of a much less than that. Provided that c is nonzero, the LCG will have a full period for all seed values if and only if:[2]

The most important piece is maybe that it’s linear. Realize the following algorithm will take only about 2^28 guesses, one for every x.

For each x[i]:
  calculate what y[i] has to be, given that x[i] ^ y[i] = output[i]
  see if x[i+1] ^ y[i+1] == output[i+1]. If so, iterate, and we have a match

The following C# program calculates this very quickly, on my machine about five seconds.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace linear_prng
{
    class Program
    {


        static void Main(string[] args)
        {
            const int MAX = 295075153;
            int[] seq = new int[] { 210205973, 22795300, 58776750, 121262470, 264731963, 140842553, 242590528 };


            for (int x = 0; x < MAX; x++)
            {
                int x_temp = x;
                for (int i=0; i < seq.Length-1; i++)
                {
                    
                    int y = x_temp ^ seq[i];
                    int x_next = (2 * x_temp + 5) % MAX;
                    int y_next = (3 * y + 7) % MAX;
                    if (seq[i + 1] == (x_next ^ y_next))
                    {
                        System.Console.WriteLine("{0}: Sol x {1} {2}", i, x_temp, y);
                        x_temp = x_next;
                        y = y_next;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            System.Console.ReadLine();
            
        }
    }
}

Plug the output into the original python program in place of the random x and y, and calculate the next number, which is: 231886864

Week 2 – Insecurity of a Two Round Feistel

Problem

Recall that the Luby-Rackoff theorem discussed in Lecture 3.2 states that applying a three round Feistel network to a secure PRF gives a secure block cipher. Let’s see what goes wrong if we only use a two round Feistel. Let F:K×{0,1}32→{0,1}32 be a secure PRF. Recall that a 2-round Feistel defines the following PRP F2:K2×{0,1}64→{0,1}64:

Feistel

Here R0 is the right 32 bits of the 64-bit input and L0 is the left 32 bits.

One of the following lines is the output of this PRP F2 using a random key, while the other three are the output of a truly random permutation f:{0,1}64→{0,1}64. All 64-bit outputs are encoded as 16 hex characters. Can you say which is the output of the PRP? Note that since you are able to distinguish the output of F2 from random, F2 is not a secure block cipher, which is what we wanted to show.

Hint: First argue that there is a detectable pattern in the xor of F2(⋅,064) and F2(⋅,132032). Then try to detect this pattern in the given outputs.

Then it gives some sample inputs and outputs

On input 0^64 the output is “2d1cfa42 c0b1d266″. On input 1^32 0^32 the output is “eea6e3dd b2146dd0″.
On input 064 the output is “7c2822eb fdc48bfb”. On input 132032 the output is “325032a9 c5e2364b”.
On input 064 the output is “290b6e3a 39155d6f”. On input 132032 the output is “d6f491c5 b645c008″.
On input 064 the output is “9d1a4f78 cb28d863″. On input 132032 the output is “75e5e3ea 773ec3e6″.

Solution

In the first round 0 is xored with the F(k1) and in the second 1 is xored with F(k1) so just looking at the first block, xor that with one and it should give us the first block of the second

This simple program does that xor

import sys

a = sys.argv[1].decode("hex")
for i in a:
sys.stdout.write("{0:02x} ".format(ord(i)^0xff))

print ""

Week 3 – Hash Collision

Problem

In this assignment your task is to find hash function collisions using the birthday attack discussed in the lecture.

Consider the hash function obtained by truncating the output of SHA256 to 50 bits, say H(x)=LSB50(SHA256(x)), that is we drop all but the right most 50 bits of the output. Your goal is to find a collision on this hash function. Find two strings x≠y such that LSB50(SHA256(x))=LSB50(SHA256(y)) and then enter the hex encoding of these strings in the fields below.

For an implementation of SHA256 use an existing crypto library such as PyCrypto (Python), Crypto++ (C++), or any other.

Solution

This code takes a few minutes, but it eventually finds a collision.



using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;
using System.Data.SqlServerCe;



namespace hash_collision
{
    class Program
    {
        //given a seed, returns the first 50 byte hash
        //woops, the assignment asks for the last
        static Int64 getTruncatedHash(int seed)
        {
            SHA256 shaM = new SHA256Managed();
            byte[] result = shaM.ComputeHash(BitConverter.GetBytes(seed));

            byte[] truncatedresult = new byte[8];
            Array.Copy(result, truncatedresult, 8);
            //last byte only car about two most significant bits, do & 0xB0
            truncatedresult[6] = (byte)(truncatedresult[6] & 0xB0);
            truncatedresult[7] = (byte)(0x00);
            return (BitConverter.ToInt64(truncatedresult, 0));

        }


        //given a seed, returns the last 50 byte hash
        static Int64 getEncatedHash(int seed)
        {
            SHA256 shaM = new SHA256Managed();
            byte[] result = shaM.ComputeHash(BitConverter.GetBytes(seed));

            byte[] truncatedresult = new byte[8];
            //Array.Copy(result, 0, truncatedresult, 23, 8);
            Array.Copy(result, 24, truncatedresult, 0, 8);
            //last byte only care about two least significant bits, do & 0x03
            truncatedresult[1] = (byte)(truncatedresult[1] & 0x03);
            truncatedresult[0] = (byte)(0x00);
            return (BitConverter.ToInt64(truncatedresult, 0));

        }

        static void printStuff(int val)
        {
            System.Console.Write("sha256(");
            byte[] seed = BitConverter.GetBytes(val);
            foreach (int i in seed)
            {
                System.Console.Write("{0:X2}", i); 
            }
            System.Console.Write(")\t");
            SHA256 shaM = new SHA256Managed();
            byte[] result = shaM.ComputeHash(seed);
            foreach (int i in result)
            {
                System.Console.Write("{0:X2}", i);
            }
            System.Console.Write("\r\n");
        }


        static void Main(string[] args)
        {

            for(int iter=0; iter<24; iter++)
            {
                Dictionary<Int64, int> mhash = new Dictionary<Int64, int>();

                //I'd much rather do 2^25, but .net throws an outofmemoryexception... too bad it's not config
                //something like Java -xMx2G, which would be nice.
                int scaler = (int)Math.Pow(2, 24);
                for (int i = scaler*iter; i < scaler*(iter+1); i++)
                {
                    Int64 fiftyhash = getEncatedHash(i);
                    if (mhash.ContainsKey(fiftyhash))                   {
                        System.Console.WriteLine("FOUND!!!!");
                        printStuff(i);
                        printStuff(mhash[fiftyhash]);
                        Environment.Exit(0);
                    }
                    else
                        mhash.Add(fiftyhash, i);

                }
                System.Console.WriteLine("Done with iteration {0} :(", iter);
                System.Threading.Thread.Sleep(500);
            }
        }
    }
}

collision

Week 4 – CBC with IV

Problem:

An attacker intercepts the following ciphertext (hex encoded):

   20814804c1767293b99f1d9cab3bc3e7 ac1e37bfb15599e5f40eef805488281d 

He knows that the plaintext is the ASCII encoding of the message “Pay Bob 100$” (excluding the quotes). He also knows that the cipher used is CBC encryption with a random IV using AES as the underlying block cipher. Show that the attacker can change the ciphertext so that it will decrypt to “Pay Bob 500$”. What is the resulting ciphertext (hex encoded)? This shows that CBC provides no integrity.

Solution:

This is insecure because the first message block is xored with the random IV

20814804c1767293b99f1d9cab3bc3e7 ac1e37bfb15599e5f40eef805488281d
P a y B o b 1 0 0 $

9th char
0xb9 decrypts to 1
0xb9 xor ascii (1 xor 5)
0xb9 xor 0x31 xor 0x35
= 0xbd

20814804c1767293bd9f1d9cab3bc3e7 ac1e37bfb15599e5f40eef805488281d

Week 4 – Padding Oracle

Problem:
 
A web site administrator found these log entries in a web server log. After some digging, the admin realized that the first log entry is an AES CBC encryption with random IV of some secret data (the ciphertext is hex encoded and appears right after the “GET /”). The secret data contains private user data that should only be known to the web site. 

After more digging the admin realized that the web site is vulnerable to a CBC padding oracle attack. In particular, when a decrypted CBC ciphertext ends in an invalid pad the web server returns a 403 error code (forbidden request). When the CBC padding is valid, but the message is malformed the web server returns a 404 error code (URL not found). To her horror, the admin realized that the log entries following the first entry are a result of a remote CBC padding oracle attack on the ciphertext in the first log entry. 

See if you can use the given log entries to recover the decryption of the ciphertext in the first log entry. Keep in mind that the first ciphertext block is the random IV. The decrypted message is ASCII encoded. 

Solution:

There are plenty of good resources about the padding oracle. My favorite is probably this: http://blog.gdssecurity.com/labs/2010/9/14/automated-padding-oracle-attacks-with-padbuster.html

#!/usr/bin/python
import sys

class oracleAnal:
    #Original doc at http://spark-university.s3.amazonaws.com/stanford-crypto/projects/proj4-log.txt
    #The file processed here generated with cat ./proj4-log.txt | egrep " 404" | cut -f2 -d/ | cut -f1 -d " " > pad.txt
    def __init__(self, fname, debug=False):
      self.debug = debug
      self.iv = []
      self.requests = []
      #need to skip the iv (e.g. block 0)
      self.currBlock = 1
      self.parseRequests(fname)  
      for i in self.iv:
        self.decryptBlock(self.requests[16*self.currBlock:16*(self.currBlock+1)], i)
        self.currBlock += 1
    
    #this parses the request file into self.iv and self.requests
    def parseRequests(self, fname):
      f = open(fname)
      requests = f.readlines()
      for i in range(0, len(requests)):
        req = requests[i].strip()
        self.requests.append(req[:32])
        if(i % 16 == 0):
          self.iv.append(req[32:])
      f.close()
      
    #takes a string, decodes it, and splits it to a byte array  
    def decodestr(self, mstr):
      #blocks should be 16 bytes
      if(len(mstr) != 32):
        print "Error"
      mstr = mstr.decode("hex")
      s = [ord(ch) for ch in mstr]
      return s
      
    #each block in the list is of the 16 byte format like
    #e.g. 202020202020202020202020202020d8
    #and iv is the previous original 16 byte crypt block
    #e.g. cac544d7942e50e1a0afa156c803d115
    def decryptBlock(self, bList, iv):
        finalBstr = ""
        if self.debug:
            print "Decrypting a block with IV ", iv
        iv = self.decodestr(iv)
        for block in bList:
            decblock = self.decodestr(block)
            for i in range(0,len(decblock)):
                byte = decblock[i]
                #error here if the valid pad found is 0x20, but can manually fix later...
                #plus it's right 255/256 times :)
                if byte == 0x20:
                    continue
                pad = byte
                padRes = 16-i
                tiv = iv[i]
                if self.debug:
                    print hex(pad), hex(padRes), hex(tiv)
                    print chr(pad ^ padRes ^ tiv)
                finalBstr = chr(pad ^ padRes ^ tiv) + finalBstr
                break
        sys.stdout.write(finalBstr)


m = oracleAnal("pad.txt")

Week 5 – Meet in the Middle

Problem (shortened to take out extras since formatting was messed up in copy)

Your goal this week is to write a program to compute discrete log modulo a prime p. Let g be some element in Z∗p and suppose you are given h in Z∗p such that h=g^x where 1≤x≤240. Your goal is to find x. More precisely, the input to your program is p,g,h and the output is x.

The trivial algorithm for this problem is to try all 2^40 possible values of x until the correct one is found, that is until we find an x satisfying h=g^x in Zp. This requires 2^40 multiplications. In this project you will implement an algorithm that runs in time roughly 240−−−√=220 using a meet in the middle attack.

(he gives an algorithm)

Now that we have an algorithm, here is the problem to solve:

p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
g = 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568
p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171

Each of these three numbers is about 153 digits. Find x such that h=g^x in Zp.

Solution

This was pretty straightforward.

import gmpy2


p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
g = 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568
p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171

def calc1(i):
    denominv = pow(g, i, p)
    denom = gmpy2.invert(denominv, p)
    tval = gmpy2.mul(h, denom)
    retval = gmpy2.f_mod(tval, p)
    return retval

def calc2(i):
    return pow(g, (2**20)*i, p)

hasht = {}
for i in range(0,2**20):
    hasht[calc1(i)] = i
for i in range(0, 2**20):
    c2 = calc2(i)
    if c2 in hasht:
        print "x0: ", i
        print "x1: ", hasht[c2]
        break

x = (((357984 * 2**20) + 787046)% p)
print x

Week 6 – RSA Poor Primes

Problem

Your goal in this project is to break RSA when the public modulus N is generated incorrectly. This should serve as yet another reminder not to implement crypto primitives yourself.

Normally, the primes that comprise an RSA modulus are generated independently of one another. But suppose a developer decides to generate the first prime p by choosing a random number R and scanning for a prime close by. The second prime q is generated by scanning for some other random prime also close to R. We show that the resulting RSA modulus N=pq can be easily factored.

Suppose you are given a composite N and are told that N is a product of two relatively close primes p and q, namely p and q satisfy
|p−q|<2N^(1/4) (*)
Your goal is to factor N.

Factoring challenge #1: The following modulus N is a products of two primes p and q where |p−q|<2N^(1/4). Find the smaller of the two factors and enter it as a decimal integer.

N = 17976931348623159077293051907890247336179769789423065727343008115 \
    77326758055056206869853794492129829595855013875371640157101398586 \
    47833778606925583497541085196591615128057575940752635007475935288 \
    71082364994994077189561705436114947486504671101510156394068052754 \
    0071584560878577663743040086340742855278549092581

Factoring challenge #2: The following modulus N is a products of two primes p and q where |p−q|<2^11*N^(1/4). Find the smaller of the two factors and enter it as a decimal integer.

N = 6484558428080716696628242653467722787263437207069762630604390703787 \
    9730861808111646271401527606141756919558732184025452065542490671989 \
    2428844841839353281972988531310511738648965962582821502504990264452 \
    1008852816733037111422964210278402893076574586452336833570778346897 \
    15838646088239640236866252211790085787877

Factoring challenge #3: (extra credit) The following modulus N is a products of two primes p and q where |3p−2q|<N^(1/4). Find the smaller of the two factors and enter it as a decimal integer.

N = 72006226374735042527956443552558373833808445147399984182665305798191 \
    63556901883377904234086641876639384851752649940178970835240791356868 \
    77441155132015188279331812309091996246361896836573643119174094961348 \
    52463970788523879939683923036467667022162701835329944324119217381272 \
    9276147530748597302192751375739387929

Solution

I only solved 1 and 2

import gmpy2
import math


class bad_rsa:
    def __init__(self, N):
        self.N = N
        self.computePrime()

    def computePrime(self):
        for i in range (1, 2**20):
            self.A = gmpy2.isqrt(self.N) + i
            self.calcX()
            if self.verify():
                print "found it!"
                print self.p
                break

    def calcX(self):
        Asquared = gmpy2.mul(self.A, self.A)
        remainder = gmpy2.sub(Asquared, self.N)
        self.x  = gmpy2.isqrt_rem(remainder)[0] 

    def verify(self):
        self.p = gmpy2.sub(self.A, self.x)
        self.q = gmpy2.add(self.A ,self.x)
        if gmpy2.mul(self.p, self.q) == self.N:
            return True
        else:
            return False


#problem 1
prob1 = gmpy2.mpz('17976931348623159077293051907890247336179769789423065727343008115' +
                   '77326758055056206869853794492129829595855013875371640157101398586' +
                   '47833778606925583497541085196591615128057575940752635007475935288' +
                   '71082364994994077189561705436114947486504671101510156394068052754' +
                   '0071584560878577663743040086340742855278549092581')
#problem 2
prob2 = gmpy2.mpz('6484558428080716696628242653467722787263437207069762630604390703787' +
                  '9730861808111646271401527606141756919558732184025452065542490671989' +
                  '2428844841839353281972988531310511738648965962582821502504990264452' +
                  '1008852816733037111422964210278402893076574586452336833570778346897' +
                  '15838646088239640236866252211790085787877')

a = bad_rsa(prob2)
raw_input("Enter Key")

Extracting Certificate Info from Things (like web services)

Disclaimer: short post today due to holiday. There’s no research here, but this is something I recently used which might be useful to others

Certificates these days are thrown around on everything. For example, if your web service auths with message security, in a soap envelope for a web service, you might see a base64 certificate and want to know info about it. In the soap request it looks something like this:

<o:Security>
   <o:BinarySecurityToken u:Id="uuid-xxxx" ValueType="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-x509-token-profile-1.0#X509v3" EncodingType="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-soap-message-security-1.0#Base64Binary">base64data....</o:BinarySecurityToken>
   ...

To view the certificate info, you can use openssl. The base64 encoding for openssl is strict, so first I paste the base64data into a file called cert.crt and convert that.

$ base64 -d cert.crt | base64 >cert2.crt

then you can add certificate flags to the beginning and end, so cert2.crt ends up looking like this

-----BEGIN CERTIFICATE-----
convertedbase64data
...
-----END CERTIFICATE-----

Now you can view all the cert info (containing validity, issuer, algorithms, serial numbers, subject names, public key, CRLs, thumbprints) with openssl

$ openssl x509 -in cert2.crt -text -noout

The square of random is less uniform (derr)

This is something obvious to statisticians but maybe less obvious to most programmers. I recently came across some code that essentially looks like this:

x = rand() #random number uniformly distributed between [0,1]
...
x= x**n #raise x to a power

The programer was for some reason assuming that x was still uniform between [0,1]. Of course, this isn’t the case. Although the domain is still between [0,1] the numbers will now be squished down closer to 0.

It is easy to analyze this with a change of variables.

The frequency distribution Fx(x) = P(X<=x)=x
Y=x^n
Fy(y) = P(Y<=y) = P(x^n<=y) = P(X<=y^(1/n) = y^(1/n) for 0<=y<=1
The density function is the derivitive
Fp(y)= (1/n)*y^-(1/n) = 1/(s*sqrt(y))

The graphs of the distributions look like this, first the one generated by rand, then one with n=2:

GPG Cheat Sheet

The gnu Privacy handbook has a ton of useful information, but I thought I’d make a quick reference for the gpg usage I use most. Especially because I was just an idiot and lost my gpg private key (though I do remember the passphrase) – this time there will be a backup!

List all keys

gpg –list-keys

print key to a file (mypublickey) – <keyid> is listed when you do list-keys

gpg -ao mypublickey.key –export <keyid>

show secret keys

gpg –list-secret-keys

backup secret keys

gpg -a –export-secret-keys <keyid> | gpg-aco myprivatkeyfile.key.gpg

Restoring the key

gpg –import {keyfile}

Restore an encrypted key

gpg –decrypt {privatekeyfile} | gpg –import

Sign a file

gpg –output doc.sig –sign doc

verify signature

gpg –output mydoc –decrypt doc.sig

Simpson’s Paradox

Statistics can be weird. Just when you’ve done the game show paradox, and the birthday paradox, there’s this. I think people in general need to realize that we as humans are just not that good at intuitively knowing probability.

From John Rice’s Statistics Textbook:

A black urn contains 5 red and 6 green balls, and a white urn contains 3 red and 4 green balls. You are allowed to choose an urn and then choose a ball at random from the urn. If you choose a red ball, you get a prize. Which urn should you choose to draw from? If you draw from the black urn, the probability of choosing a red ball is 5/11 (the number of ways you can draw a red ball divided by the total number of outcomes). If you choose to draw from the white urn, the probability of choosing a red ball is 3/7, so you should choose to dra from the black urn.

Now consider another game in which a second black urn has 6 red and 3 green balls, and a second white urn has 9 red and 5 green balls. If you draw from the black urn, the probability of a red ball is 6/9, whereas if you choose to draw from the white urn, the probability is 9/14. Again, you should choose to draw from the black urn.

In the final game, the contents of the second black urn are added to the first black urn, and the contents of the second white urn are added to the first white urn. Again, you can choose which urn to draw from. Which should you choose? Intuition says choose the black urn, but let’s calculate the probabilities. The black urn now contains 11 red and 9 green, so the probability of drawing a red ball from it is 11/20 = .55. The white urn now contains 12 red and 9 green balls, so the probability of drawing a red ball from it is 12/21 = .571.  So, you should choose the white urn.

When you think about it, it actually makes sense. Because the number is greater in the second one it sort of evens out. Still, a little weird though.

Another common example is in batting averages. Here is an example wikipedia gives. In this example, David Justice has a better batting average than Mike Jeter for two years in a row, but his cumulative batting average is worse.

1995 1996 Combined
Derek Jeter 12/48 .250 183/582 .314 195/630 .310
David Justice 104/411 .253 45/140 .321 149/551 .270

Actually, the batting averages make it more intuitive for me.

modular exponentiation python program

This is a simple – not efficient – but doable way to do modular exponentiation

#!/usr/bin/python

def modexp(base, pow, mod):
  exponent = 1
  i = 0
  while i < pow:
    exponent = (exponent * base) % mod
    i += 1
  return exponent

if __name__ == "__main__":
  import sys
  print modexp(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))

Example usage

$ modexponent.py 2 1234 789
481

For large numbers this method isn’t practical. The below program implements the improved python algorithms for modular exponents.

#!/usr/bin/python
#Let x be an integer written in binary, y and n be integers
#I'm sure this isn't the best, but this is only called once per program
def binconvert(n):
  barray = []
  if n < 0: 
    raise ValueError, "must be positive"
  if n == 0:
    return 0
  while n > 0:
    #barray = n%2 + barray[:]
    barray.append(n%2)
    n = n >> 1
  barray.reverse()
  return barray
#this is the intuitive but slow way
def modexp(base, pow, mod):
  exponent = 1
  i = 0
  while i < pow:
    exponent = (exponent * base) % mod  
    i += 1
  return exponent
#y**x mod n
def modexp1(y, x, n):
  #convert x to a binary list
  x = binconvert(x)
  
  s = [1]
  r = x[:]
  for k in range (0, len(x)):
    if x[k] == 1:
      r[k] = (s[k] * y) % n
    else:
      r[k] = s[k]
    s.append ((r[k]**2)%n)
  #print s
  #print r
  return r[-1]
#similar to modexp1 except uses the bits in reverse order
def modexp2(y, x, n):
  a = x
  b = 1
  c = y
  while a != 0:
    if a % 2 == 0:
      a = a/2
      c = (c**2) % n
    else:
      a = a -1
      b = (b * c) % n
  return b
if __name__ == "__main__":
import sys
  print modexp(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))
  print modexp1(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))
  print modexp2(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))

Using the above program, some interesting things are easy to demonstrate. For example, here is a test that shows for 100,000 tries, the 2 algorithms get the correct answer.

import prob23
import random
import sys

BASEMAX = 60000
EXPMAX = 60000
MODMAX = 100000
ITERATIONS = 100000

print "beginning program"
print "This will take awhile... you need", ITERATIONS, "of these dots to complete."
p
for i in range (0, ITERATIONS):
  if i % 10 == 0:
    sys.stdout.write(".")
    sys.stdout.flush()
  r_base = random.randint(1, BASEMAX)
  r_exp = random.randint(1, EXPMAX)
  r_mod = random.randint(max(r_base, r_exp), MODMAX)
  trueval = prob23.modexp(r_base, r_exp, r_mod)
  testval1 = prob23.modexp1(r_base, r_exp, r_mod)
  testval2 = prob23.modexp2(r_base, r_exp, r_mod)
  if trueval != testval1 or trueval != testval2:
    print "One of these exponent things doesn't work"
    #sys.exit(1)
print "Done, all of these answers were the same."

Running this program several times with various parameters verifies the correctness of the algorithm (like how an Engineer verifies things).

Also, it’s interesting to time these algorithms when compared to the brute force method (multiplying every number). All three algorithms were timed to find a solution. Below is some example code that accomplishes this (this particular code is for the brute force version, but it is almost identical to the other algorithms – the only change is the modexponent call).

import modexponent

for i in range(1, 65538):
  thistry = modexponent.modexp(3, i, 65537)
  if thistry == 2:
    print i
    break
  if i % 15000 == 0:
    print "trying", i

Running all three algorithms, the results are shown below.

me@Opteron:~/math/chp3$ time python bruteforce.py
55296
real 11m28.131s
user 11m18.710s
sys 0m1.170s
me@Opteron:~/math/chp3$ time python algorithm1.py
55296
real 0m3.285s
user 0m3.290s
sys 0m0.000s
me@Opteron:~/math/chp3$ time python algorithm2.py
55296
real 0m2.621s
user 0m2.610s
sys 0m0.010s

This is a huge speedup – from 11 minutes in the case of brute forcing to under 4 seconds for the two algorithms.

Follow

Get every new post delivered to your Inbox.

Join 36 other followers