Correlation attack on a simple toy stream-cipher

Let us assume a simple toy stream cipher (it could be any of the famous GSM A5/1, Bluetooth E0… stream ciphers) but with 5 registers defined by the following primitive polynomials

p[1] = x2 +               x + 1 ;          11
p[2] = x3 +               x + 1 ;         101
p[3] = x4 +               x + 1 ;       1001
p[4] = x7 +               x + 1 ;  1000001
p[5] = x8 + x7 + x2 + x + 1 ; 11000011

and a non-linear combining function f defined below

f = x1•x2•x3•x4•x5 ⊕ x4•x5 ⊕ x5;

And let’s say we know the first 32 bytes of the clear-text and cipher-text. From these we can retrieve the key-stream used for the first 32 bytes of clear-text as follows

key-stream = clear-text ⊕ cipher-text

Now we have 256 bits of key-stream. What do we want? Well, we want to know the initial states of the 5 registers so that we will be able to break later communications after the 256th bit. How can we do that? One way is to brute force all the possible value combinations of the 5 registers. That is 28 * 27 * 24 * 23 * 22 = 224 number of checks. If the polynomials were of higher order, brute forcing wouldn’t be feasible. So we need another technique to minimize our work. Now we need to see the correlation between the registers and all possible values of combining function. We use Truth Table of five variables and a 6th column holding output of f. Then we compare the output of each register and the 6th column for matches.

  R1 

 R2

  R3

  R4 

  R5

f

0 0 0   0   0   0
0 0 0 0 1 1
0 0 0 1 0 0
0 0 0 1 1 0
0 0 1 0 0 0
0 0 1 0 1 1
0 0 1 1 0 0
0 0 1 1 1 0
0 1 0 0 0 0
0 1 0 0 1 1
0 1 0 1 0 0
0 1 0 1 1 0
0 1 1 0 0 0
0 1 1 0 1 1
0 1 1 1 0 0
0 1 1 1 1 0
1 0 0 0 0 0
1 0 0 0 1 1
1 0 0 1 0 0
1 0 0 1 1 0
1 0 1 0 0 0
1 0 1 0 1 1
1 0 1 1 0 0
1 0 1 1 1 0
1 1 0 0 0 0
1 1 0 0 1 1
1 1 0 1 0 0
1 1 0 1 1 0
1 1 1 0 0 0
1 1 1 0 1 1
1 1 1 1 0 0
1 1 1 1 1 1

We see that register 5 is correlated to f (25/32 matches). Note that we can exploit the correlation of other registers as well. If we used both register 5 and other correlated register together, our final brute force attack would be significantly fast. But for now, let’s just take register 5 only and brute force the rest of the registers. Now that we know register 5 is correlated, we try all the 256 possible values of it to find the one that results with the maximum match with the key-stream. We use the following simple C code

for (i=1; i<256; i++) {
	ivR5 = i;
	for (j=0; j<256; j++) {
		R5 = (ivR5&1)==1?1:0;
		lfsr(polyR5, &ivR5, 1, 8);
		r5[j]=R5;
	}
	match = 0;
	for (j=0; j<256; j++) {
		if (r5[j] == key_stream[j]) match++;
	}
	matches[i] = match;
}

After this run, matches[] contains the number of matches of the key-stream and the output of all possible values of register 5. Note that the lfsr() function is a modified version of Linear Feedback Shift Register (LFSR) taking the polynomial, the initial value of the register, the number of bits to output and the length of the polynomial as argument and returns the output of the register (1 or 0). Now we need to select the maximum as follows

for (i=0; i<max_match; i++) {
		max_match = matches[i];
		idx_max = i;
	}
}
// idx_max will hold the initial value of R5

At this step we have the initial value of register 5. We can proceed to 27 * 24 * 23 * 22 = 216 checks for the rest of the registers (in reality, this would be significant as we eliminated the register with the highest degree). A sample code could look like the following for brute forcing the other registers.

 
        ivR5 = idx_max;
	for (i=1; i<128; i++) {
	   for (j=1; j<16; j++) {
              for (k=1; k<8; k++) {
		  for (l=1; l<4; l++) {					
		     ivR4 = i;
		     ivR3 = j;
		     ivR2 = k;
		     ivR1 = l;
		     .
		     .
		     .

By now we have the initial values of the 5 registers. We can decrypt and read any communication between the two parties without knowing the symmetric key they used to generate the key-stream. Cheers!

Sources of dangerous vulnerabilities

There are a lot of whitehat and blackhat security researchers out there. While the whitehat researchers inform the target company before disclosing vulnerabilities, the blackhats either use the vulnerabilities for personal activities or sell them on black market. But both kinds of researchers spend a lot of time stepping through codes around where potential vulnerabilities might exist (e.g. around input manipulation code in a hunt for buffer overflow or format string vulnerabilities).

But there are a couple of other potential tricks to facilitate the hunt. One of this is comparing binaries of critical updates that are pushed by the vendor. If we consider Windows as an example, if Microsoft pushed a critical update, say, for one of the services handled by svchost.exe, an attacker may compare the old binary with the new updated version to see where Microsoft patched the vulnerabilities. In some cases reverse-engineering the patch might also reveal the vulnerabilities. The vulnerabilities found might interest the attacker if they have remote code execution ability, local privilege escalation or any arbitrary code execution. Since not all people update their system as soon as the update is pushed, the attackers will have enough time to craft their exploit and start using. If I remember correctly, the Sasser worm (2004) used the vulnerability discovered in this way to exploit MS04-011.

The other potential source of information is Dr. Watson of Windows. When applications crash, the error reporting feature on Windows XP and later versions might leak some important information on source of error. A reverse-engineering around the location might provide information about a vulnerability in the target application. Gathering the error reporting might be done on a lab computer or from different compromised computers.

These definitely are not going to be the only ways to identify vulnerabilities from binaries.

You’re a money mule and you don’t know it?!

When I hear a news like “40 million credit card details stolen“, I used to wonder how the hackers cash out and get the money on their hands. Since it is traceable, they cannot buy anything or transfer the money. Let’s face it, hacking the accounts might be “easy” but getting the money is a bit challenging. So how do they get the money? Some of the hackers sell the credit card or bank account details to third parties to avoid the risk of getting caught while cashing out. Imagine stolen 40 million credit cards details sold at $20 each; it is still worth it for the hackers. But the story is still not complete. How do the people who bought the details get the money then? Transferring still will not work because it is traceable. Sell it to somebody else? Maybe. Keep reading.

Recently, somebody told me that he found an online job from a credible source. He told me that some people contacted him through e-mail claiming they read his CV on a career search website. And since he recently posted his CV on the website, he thought they are 100% legit. They offered him a very good salary for something that didn’t need much of his time; a 10% commission on each transaction and bonus. They also promised him a raise after the first 1 month of probation period. He was happy about it and filled in some forms and started the job. What does he have to do? Simple, give out his bank details (normally IBAN but they said he will have extra 200 euro bonus if he hands over his username and password for his online banking which obviously is to steal money from his bank account), then they will transfer him some money, then he has to withdraw 90% of the money (10% is his commission) and send it to them via Western Union. Money laundrying made easy!

But what is really going on? OK, here is the deal.  These people have a lot of stolen accounts on their hands. Since they cannot transfer the money to their account, for obvious reasons, they hire somebody (called money mule) to do the risky job. This guy told me he thought he was working with a 20+ years old financial company. Normally, since the person who is hired does not know he is doing a crime, he will go to his bank, withdraw the money and send it to the thieves. In order to avoid being traced, these people might have a fake identity to claim the money from Western Union (or related service). The money is gone. When the person who was stolen reports to the police, the police asks the bank and the bank says there was a transfer to this account. It is only the mule that will be caught while the original thieves are enjoying the money.

After doing a little research I found out that most of the thieves are from Eastern Europe. In fact, the guy told me he was supposed to send the money to Ukraine. I also noticed that most frauds (be it the Nigerian 419 scam) involve Western Union. Couldn’t this problem be minimized if Western Union outlets had asked some questions where the money came from before accepting and sending the money when the destined person resides in these countries? Off the top of my head, it seems a solution to me.

Have you ever been a money mule? Or do you know someone who was a money mule?

X11 based Linux keylogger

As a challenge to the paper “Unprivileged Black-Box Detection of User-Space Keyloggers“, we were askd to write a Linux keylogger that can hide behind the tool mentioned on the paper. A friend and I came up with several ideas to hide our keylogger from being detected. We didn’t manage to include all the ideas in the keylogger code because of time constraint but the professor approved that if we had included those options, their tool wouldn’t have detected it. Before writing the ideas we came up with, let me explain how their detection method works in a nutshell.

They assumed that, by design, keyloggers capture keystrokes and save them to file. If for example, “AbCdeF” was pressed on the keyboard, somewhere, some process is writing a file with the same bytes. So they check for this correlation by sending keys to all running processes and monitoring file activities and checking the number of bytes written. If the same amount of bytes were written to file, then the process that wrote that file is a keylogger.

Our ideas to circumvent this are presented below. Obviously, these are for educational purpose only.

1. Buffering.  We have a buffer that changes its size every time it writes its content to file. Here is how it works.

Let’s say we have buf[1024]. And let the first random buffer size be 750. Then we keep buffering until 750 is reached and write it to file. Then the next buffer size would be randomly chosen. Say 900. The process continues like that.

2. If we’re on an Internet-connected computer, we directly post the logged keystrokes on a remote server. That’s it, nothing on file.

3. Being selective when we capture keys. Let’s face it, when we capture keys, usually it’s password or something related. So why would we be interested in keys that are entered on Sublime? So, we targeted web browsers: Mozilla Firefox and Google Chrome. What does it mean? Their tool sends our keylogger a key and it is ignored. Keeps logging like a boss 🙂

There were also other ideas like having a different sized output (different size than the entered keys) on file by applying cryptography but the paper says they addressed this issue very well so we didn’t bother to test it. Will post code if anybody is interested.

The C source code of X11 based Linux keylogger can be found here.

This work got us full points.

 

IRC Remote Controller for uTorrent in C

Few years ago, I made an IRC bot uTorrent remote controller for personal use. There was no such tool during that time (even now, I think) but I badly needed it. The ideal case where you need this tool is for example when you run your torrent client on an office/school computer and you don’t have port forwarding (or you don’t have a static private IP) and you cannot control your torrents using the remote control that ships with uTorrent but you want to control your torrents from home. Let’s say you want something downloaded and you are at home (or anywhere), so you just go to some IRC channel on some server (configurable) and talk to the bot. Current features are adding new torrent (via direct URL), pausing, stoping, deleting and viewing status. A typical command looks like the following:

!add hxxp://www.somesite.com/sometorrentfile.torrent
!stat
[1] Some.File                                       700MB   340KB/s  68%
[2] Some.Other.File                       110MB   240KB/s  24%

Where the status is shown in different color background depending on the kind (stopped, paused, active). The bot joins the channel with random nick because when connection is interrupted for few minutes and comes back online, the bot cannot join using the old nick. This is because the server thinks the nick is in use until the PING request times out for the previous bot. In order to avoid this problem, each time the bot joins a channel, it uses a random nick. If the bot is in a bad connection, we might see many bots from the same machine but only one is active. The rest will leave the channel when they don’t respond to the server request in time.

Source code can be found here: https://github.com/biniamf/utorrent_irc_bot

Ciao!

Model checking using iSpin on Windows

Ever tried to do model verification using iSpin (on Windows) on a click of a button but couldn’t manage to get it to work? I had the same problem. Apparently, there aren’t good resources that solve this problem. Follow these steps to get it to work. This has been tested to work on Widnows 7 and Windows 8.

I assume you have iSpin and SPIN installed on you system. Now let’s proceed with the necessary components. While doing the command line verification, most probably you used Cygwin’s gcc. or if you haven’t done any model verification so far, please first download and install Cygwin (note that you can also use MinGW instead of Cygwin – but this solution works for both). Then download and install gcc – C, C++ compiler package. When the installation completes, click on the Start menu, then right click on Computer and click on Properties. On the left navigation, click on Advanced system settings — a dialog will appear. On the dialog, click on Environmental Variables. Now a new dialog will open. Under the System variables section, locate the variable Path, select it and click on Edit. At the end of Variable value, add semi-colon (;) and add the path where you installed Cygwin plus Bin folder. That is, if you installed Cygwin in C:\Cygwin, then add the following

C:\Cygwin\Bin\

If you’re using the MinGW version of gcc rather than Cygwin, use instead the following (assuming MinGW is installed in C:\MinGW\)

C:\MinGW\bin\

and click on OK. Then click on OK on the previous dialogs.

Now, navigate to the path where you installed SPIN. Locate iSpin, then open it in a text editor (I used Notepad++). Now locate the line that reads the following:

set CC      gcc

Add the following line just under it (select the one that applies for you)

set CC      “C:/Cygwin/bin/gcc”          ; for Cygwin users

set CC      “C:/MinGW/bin/gcc”          ; for MinGW users

That’s it. Save the file and close it. Now as a test, open iSpin and then open some model. Then write the LTL properties you want to verify inside the model, save it, and reopen it. Then go to the verification tab and adjust the commands to be used as per your requirements. Then click on the Run button. After some time, you should see the result on the Verification result window (the dark windows on the right bottom).

Cheers!