Common .NET ViewstateUserKey CSRF Issue

I’ve added the 2013BH tag to all posts related to my recent Blackhat EU talk – more posts are coming, and I’ll post the whole talk and finished whitepaper relatively soon. To understand this post, reviewing MVC .NET CSRF issues and Problems with triple submit cookies may be useful.

The most common advice for mitigating CSRF in .NET web applications is to set ViewStateUserKey to sessionID. This is an extremely common CSRF defense. At the time of this writing, something like this is present in the OWASP prevention cheat sheet as well as the Microsoft SDL. The following is a snippet from OWASP.

ViewState can be used as a CSRF defense, as it is difficult for an attacker to forge a valid ViewState. It is not impossible to forge a valid ViewState since it is feasible that parameter values could be obtained or guessed by the attacker. However, if the current session ID is added to the ViewState, it then makes each ViewState unique, and thus immune to CSRF.
To use the ViewStateUserKey property within the ViewState to protect against spoofed post backs. Add the following in the OnInit virtual method of the Page-derived class (This property must be set in the Page.Init event)
if (User.Identity.IsAuthenticated)
ViewStateUserKey = Session.SessionID; }

Unfortunately, this recommendation doesn’t always work for similar reasons to MVC. To clarify what the sessionID is: it is just a cookie, and it’s a cookie that isn’t always used for authentication. As already mentioned, most large scale sites tend to use custom authentication. Microsoft sites tend to use LiveID much more frequently than simple forms based auth. As should be obvious from the previous posts, if the sessionID isn’t used for authentication then this cookie can simply be overwritten by using an attacker cookie and an attacker ViewState. This attack is most useful with lateral escalation, meaning with one account on an application, you can CSRF other users of the application.

This is a super common problem in my experience. To illustrate this for Blackhat I wrote a sample app that’s not worth showing. It sets the ViewStateUserKey to the sessionID and uses ACS for authentication similar to how this tutorial describes (the only difference is this app uses Forms rather than MVC).

This pic shows the cookies sent immmediately after authenticating with ACS. Although ASP.NET_SessionId is automatically set, it has nothing to do with the authentication of the web application.

cookie

To understand how this attack works, perform the following steps on an ASP.net forms based application using ACS for auth.

  1. Create two users, user_victim and user_attacker where VIEWSTATE is used as a CSRF mitigation and ViewStateUserKey = SessionID.
  2. As user_attacker, capture the POST values. This will include several ASP.NET specific VIEWSTATE fields which are used to prevent CSRF. Also, capture the ASP.NET_SessionId cookie.
  3. As user_victim, replace the POST values with the values captured in request 2. This request will fail with a 500 (Validation of viewstate MAC failed), because ViewStateUserKey = SessionId. Otherwise, this could be used to exploit classic CSRF.
  4. However, if we cause the application to consume user_attacker’s ASP.NET_SessionId cookie rather than user_victim’s cookie, the request will go through.

In terms of exploitability, this is again equivalent to naïve double submit. An attacker needs the ability to write cookies (e.g. find XSS in a neighboring sub domain or be in the middle), but in many cases this is exploitable.

There are several ways to mitigate this. The most straightforward is to, after authentication, set the ViewStateUserKey to the cookies actually used to tie the user to a session. In the example above, ViewStateUserKey could be set to the FedAuth cookie. Unfortunately, this type of thing can be difficult to tie into the framework or detect with static analysis tools because these things have no way of knowing how exactly custom authentication works.

ValidateRequest should probably still be Enabled

I noticed this post on reddit a couple weeks back, and it’s called “new .net xss bypass”. I look at .net apps more than anything else right now as part of my day job, so this new bypass is something I was already aware of. There are quite a few comments I think are a bit off, and the article calls this a “vulnerability”. This is an interesting subject, and like a lot of things, people say things that can be misleading or not tell the entire story…

What is validateRequest?

validateRequest kind of works like a WAF, and it’s main purpose is to mitigate reflected XSS. It’s enabled by default, and you can see it in action on most .NET websites. For example, check out http://windows.microsoft.com/en-US/windows/home. If you send it http://windows.microsoft.com/en-US/windows/home?myparam=aaa or http://windows.microsoft.com/en-US/windows/home?myparam=aaa%3c it’s fine, but then if you send it http://windows.microsoft.com/en-US/windows/home?myparam=aaa%3ca it gives an error (note the only difference between the last two is < vs <a). What's going on here?

Well, on the server, the stack trace probably looks something like this (this is what it looks like in my test application).

[HttpRequestValidationException (0x80004005): A potentially dangerous Request.QueryString value was detected from the client (test="<a").]
   System.Web.HttpRequest.ValidateString(String value, String collectionKey, RequestValidationSource requestCollection) +9665149
   System.Web.<>c__DisplayClass5.<ValidateHttpValueCollection>b__3(String key, String value) +18
   System.Web.HttpValueCollection.EnsureKeyValidated(String key) +9664565
   System.Web.HttpValueCollection.GetValues(Int32 index) +29
   System.Web.HttpValueCollection.ToString(Boolean urlencoded, IDictionary excludeKeys) +206
   System.Web.UI.Page.get_ClientQueryString() +411
   System.Web.UI.HtmlControls.HtmlForm.GetActionAttribute() +259
   System.Web.UI.HtmlControls.HtmlForm.RenderAttributes(HtmlTextWriter writer) +724
   System.Web.UI.HtmlControls.HtmlControl.RenderBeginTag(HtmlTextWriter writer) +41
   System.Web.UI.HtmlControls.HtmlContainerControl.Render(HtmlTextWriter writer) +20
   System.Web.UI.HtmlControls.HtmlForm.Render(HtmlTextWriter output) +53
   System.Web.UI.Control.RenderControlInternal(HtmlTextWriter writer, ControlAdapter adapter) +57
   System.Web.UI.Control.RenderControl(HtmlTextWriter writer, ControlAdapter adapter) +100
   System.Web.UI.HtmlControls.HtmlForm.RenderControl(HtmlTextWriter writer) +40
   System.Web.UI.Control.RenderChildrenInternal(HtmlTextWriter writer, ICollection children) +128
   System.Web.UI.Control.RenderChildren(HtmlTextWriter writer) +8
   System.Web.UI.Control.Render(HtmlTextWriter writer) +10
   System.Web.UI.Control.RenderControlInternal(HtmlTextWriter writer, ControlAdapter adapter) +57
   System.Web.UI.Control.RenderControl(HtmlTextWriter writer, ControlAdapter adapter) +100
   System.Web.UI.Control.RenderControl(HtmlTextWriter writer) +25
   System.Web.UI.Control.RenderChildrenInternal(HtmlTextWriter writer, ICollection children) +128
   System.Web.UI.Control.RenderChildren(HtmlTextWriter writer) +8
   System.Web.UI.Page.Render(HtmlTextWriter writer) +29
   System.Web.UI.Control.RenderControlInternal(HtmlTextWriter writer, ControlAdapter adapter) +57
   System.Web.UI.Control.RenderControl(HtmlTextWriter writer, ControlAdapter adapter) +100
   System.Web.UI.Control.RenderControl(HtmlTextWriter writer) +25
   System.Web.UI.Page.ProcessRequestMain(Boolean includeStagesBeforeAsyncPoint, Boolean includeStagesAfterAsyncPoint) +6704
   System.Web.UI.Page.ProcessRequest(Boolean includeStagesBeforeAsyncPoint, Boolean includeStagesAfterAsyncPoint) +245
   System.Web.UI.Page.ProcessRequest() +72
   System.Web.UI.Page.ProcessRequestWithNoAssert(HttpContext context) +21
   System.Web.UI.Page.ProcessRequest(HttpContext context) +58

Tracing down the line from the validateString method, eventually it calls this for all values (not keys).

// System.Web.CrossSiteScriptingValidation
internal static bool IsDangerousString(string s, out int matchIndex)
{
	matchIndex = 0;
	int startIndex = 0;
	while (true)
	{
		int num = s.IndexOfAny(CrossSiteScriptingValidation.startingChars, startIndex);
		if (num < 0)
		{
			break;
		}
		if (num == s.Length - 1)
		{
			return false;
		}
		matchIndex = num;
		char c = s[num];
		if (c != '&')
		{
			if (c == '<' && (CrossSiteScriptingValidation.IsAtoZ(s[num + 1]) || s[num + 1] == '!' || s[num + 1] == '/' || s[num + 1] == '?'))
			{
				return true;
			}
		}
		else
		{
			if (s[num + 1] == '#')
			{
				return true;
			}
		}
		startIndex = num + 1;
	}
	return false;
}

Obvious Edge Cases

So clearly, validateRequest makes no attempt to stop most DOM XSS, and there’s no attempt at all with stored XSS. It’s also clearly limited in preventing reflected XSS too. There’s no attempt at detecting encoding, so there’s kind of an assumption that the encoding is UTF-8. Not to mention if there’s an xss in the whole query string, in which case you could just put it in the keys. Not to mention if there’s user input being reflected in the context of an attribute, validateRequest does not stop it. For example:

<img src="" title="USERINPUT">

In this context, validateRequest doesn’t stop reflected XSS. It does, however, try to stop at least this case:

<html><body>
USERINPUT
</body></html>

If you can get script to execute in this context with UTF-8 encoding, you’ve bypassed something validateRequest was meant to prevent.

The bypass I saw on reddit

The bypass looks like this:

‹%tag style="xss:expression(alert(123))" ›

This can make it through validateRequest’s filter because the < is not followed by a bad char (% is fine). The tags execute in IE9 in compatibility mode in the context above (it doesn’t seem to execute in IE 8- or IE 10).

There are some limitations in this attack though. First, remember we’re talking about just IE9. Second is the fact that by default IE9’s xss filter is turned on, and IE 9's xss filter will prevent the above from executing. There might be a generic way to bypass both validateRequest and IE9’s xss filter, but I am not aware of it.

IE_filter

Things I’ve Tried

In the past, I’ve tried a few bypasses of validateRequest myself.

Unit Test with single separators

I’ve tried the following test cases. This does catch the <% bypass with IE9 in compatability mode, but nothing else fires. One thing that I thought was a bypass at first was %00, but validaterequest does actually catch that.

def bad_char(m):
    if (m == "<" or m== "!" or m == "?" or m == "/" or (ord(m) >= 0x41 and ord(m) <= 0x5a) or
        (ord(m) >= 0x61 and ord(m) <= 0x7a)):
        return False
    return True

def singlechars_img(f):
    for i in range(1,256):
        if not bad_char(chr(i)):
            continue
        f.write("<" + chr(i) + "img src='' onerror=alert(" + hex(i) + ") /> <br />\n")

def singlechars_style(f):
    for i in range(1,256):
        if not bad_char(chr(i)):
            continue
        f.write("<" + chr(i) + "tag style=\"xss:expression(open(alert(" + str(i) + ")))\" > <br />\n")

Trying to be clever (overlong UTF-8, etc)

One thing I tried was to backspace one of the tags with the ascii value 0x08: <<0x08script>. This doesn’t execute in any browser tried

I tried the shift JIS prefix code %e0 which should consume the next character as part of a multibyte literal. The idea is that if validaterequest tries to decode any data, it may consume an extra %3c, whereas some browsers (like chrome) do not consume an extra %3c and there would be a mismatch. But validaterequest is much simpler, and just iterates over all the bytes like we can see from the reflected snipped above.

I also tried several overlong UTF-8 combinations, but these don’t execute with content-type UTF-8

#overlong UTF-8
def overlong(f):
    #attempt to delete a <
    f.write("<<\x08script>alert(1)</script>")
    #some overlong UTF
    f.write("<\xFC\x80\x80\x80\x81\xA9\xFC\x80\x80\x80\x81\xAD\xFC\x80\x80\x80\x81\xA7 src='' onerror=alert(2) />")
    f.write("<\xFC\x80\x80\x80\x81\xA9mg src='' onerror=alert(2) />")
    f.write("\xC1\xA9mg src='' onerror=alert(3) />")
    f.write("\xF8\x80\x80\x81\xA9mg src='' onerror=alert(3) />")

Conclusions

The ‹%tag style=”xss:expression(alert(123))” › validaterequest bypass is interesting and something to keep in the back of your pentesting pocket, but if you’re on defense don’t panic. I don’t think this really breaks validaterequest in a meaningful way. Pulling numbers out of my ass, I would say that if 30% of xss were prevented by validaterequest without this, then maybe this knocks the successfully prevented attacks down like a percent or two, to 28% (exploitable against users who use IE9 and have disabled the xss filter (or where you can get around the xss filter)). validaterequest does have it’s problems, and there have been generic bypasses in the past, but I think it’s still worthwhile to enable.

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

Calculating an Integer Overflow

I was playing an exploit game yesterday, and had to compute an exact value for an integer overflow, which made me think (when I’ve run into this before, I’ve just had to get ‘close enough’). In the binary, it compares some user input to the integer 9, which it must be “less than”

call _atoi
mov [ebp+var_C], eax
cmp [ebp+var_C], 9
jle short loc_8 ; process input and reach overflow

n is then multiplied by 4 to make room for 9 ints

shl eax, 2

var_c is then used as the n parameter in memcpy

void *memcpy(void *dest, const void *src, size_t n);

The vulnerability is possible (at least in part) to the shl, which can be used to wrap the integer and bypass the jle check. It’s fairly obvious there is an integer overflow here, and in fact, calculating n to be an exact value is also not difficult. So in my case I wanted n in the memcpy call to equal exactly 80.

The very first thing I did was to look at this http://en.wikipedia.org/wiki/Two’s_complement, which I remember having to do in school. It’s not complicated, but once you start throwing algebra in… anyway, so instead of using math I just wrote a wrapper program on the same machine.

#include <limits.h>
#include <stdio.h>

void main()
{
  //this should be 80. Sanity check
  int y =  -INT_MAX - INT_MAX + 78;
  printf("%dn", y); 

  printf("%dn", INT_MAX);
}

which prints

2147483647
80

Then just plop this in a calculator. Remember to divide by 4 to undo the multiply

>>> (-2147483647*2 + 78)/4.0
-1073741804.0

I entered this in the appropriate place, and set a breakpoint on the call to memcpy.

(gdb) x/d $esp+8
0xbffff2b8: 80

Success, we’ve managed to set n to 80. This one took more time to write out than to solve, but hey, maybe it will be useful for someone. Plus I needed a filler today… I have some cool stuff I’m working on, but it won’t be ready until at least next post, or maybe the post after :)

Follow

Get every new post delivered to your Inbox.

Join 33 other followers