Crypto Series: New Directions in Cryptography
As some of you might have noticed already by looking at the title, this post will be the first one talking about public key cryptography. Today, I'll introduce the basic ideas around public key crypto and the ideas proposed by Diffie and Hellman in their famous paper 'New Directions in Cryptography' from 1976.
In subsequent posts, we well look at the discrete logarithm problem and the factorization problem. We'll also look into some public key cryptosystems, such as El-Gamal and RSA. And after that, we'll look at Elliptic Curve Cryptography. With all this, the algorithms part of this series will be considered closed and I'll move into cryptographic systems and protocols ;-). Stay tuned!
Crypto Series: Authentication codes
This time we'll treat two well known techniques used to solve a common problem in cryptography: authentication. To put it simple, authentication is the process of establishing an identity or a message's origin.
To achieve this using symmetric cryptography, two basic mechanisms exist. The first of them, commonly referred to as Message Authentication Codes (MAC), is based on using block ciphers with a shared key between the party claiming an identity (or sending a message) and the party verifying the identity or the origin of the message.
The second one, known as Hashed Message Authentication Codes (HMAC) is based on the use of a hash function together with some shared key. In the remaining of this post, I briefly describe the basic idea behind these two ways of assuring message authentication.
Message Authentication Codes using block ciphers
A common way to authenticate messages is to use a block cipher, such as DES, in a mode of operation which makes the latest encrypted block dependent on both the key and all the previous plaintext blocks. For instance, one can think of using 3DES in CBC mode to create a MAC over a message: encrypt the message in CBC mode using 3DES with the shared key, get the last output block and attach it to your original message.
When the recipient gets the message with its MAC, it does the same operation: encrypt each block using CBC mode and takes the last block. The result is compared against the MAC attached to the message: if there is a match, the sender of the message must have known the key (unless the encryption used is broken).
Despite being one of the most popular techniques for MAC generation (if not the most popular), CBC-MAC has some security problems and other techniques exist. For instance, you can take a look at Special Publication 800-38B by NIST.
Hashed Message Authentication Codes
HMAC is a standardized way of using hash functions for authentication purposes. The idea is to incorporate the usage of a key into a hash function, in such a way that the resulting hash could not be produced without knowing the key.
The obvious choices of prefixing the message with the key or appending the key after the message before computing the hash have security problems (see Stop using unsafe keyed hashes, use HMAC by Nate Lawson). Therefore, a slightly more complex structure was invented to avoid such problems.
The HMAC construction is defined as follows:
Where opad (outer pad) is the constant 0x5c...5c and ipad (inner pad) is the constant 0x36...36. These constants, as well as the key, are of the same length as the hash function's block length.
With this, one would follow the same approach as with any MAC: compute the HMAC value for the given message, and send it attached to the message. The recipient will perform the same computation, and if it matches the one attached to the message he will conclude that the message was sent by someone who knows K (which is hopefully only the person/entity he shared it with 😉 ).
This concludes my introduction to authentication codes. If you are looking for a good security analysis on HMAC functions, wait for Nate's post because I'm sure it will be very interesting.
Crypto Series: Cryptographic hash functions – SHA-2
So far, we've looked at block and stream ciphers in this series, including examples of each of them. Before going into asymmetric crypto I want to explain a little bit about cryptographic hash functions and some of their applications. We'll look at hash functions in general and at the SHA-1 hash function as an example.
Note that I'll often skip the 'cryptographic' adjective throughout this series of posts, but I'll always refer to cryptographic hash functions and not to regular hash functions. And as usual, this is by no means complete but just tries to give a basic understanding of what hash functions are and how they usually look like.
I must say I never studied hash functions too deeply, so this stuff will serve as a reminder for me as well. If something is not as accurate as you'd hope for, let me know in the comments ;-).
Cryptographic Hash functions: properties
A cryptographic hash function is defined as a series of operations over an input message of arbitrary length, producing an output of fixed length (hash or message digest) such that a change to the message would not come unadvertised. It should be easy to compute a hash function from a message, but given a hash value it should be infeasible to find a message that would produce that value. Further, given a message it should be infeasible to find a second message producing the same message digest and as I stated before, it should be infeasible to modify a message without modifying its hash value.
Therefore, the desired properties of a cryptographic hash function are as follows:
- Preimage resistance: given a hash value h, it should be infeasible to find a message m with h=hash(m). Otherwise the function would be vulnerable to preimage attacks
- Second preimage resistance: given a message
it should be infeasible to find a second message,
which provides the same message. I.e., given
. Otherwise, the function is said to be vulnerable to second preimage attacks.
- Collision resistance: It should be difficult to find two messages with the same message digest. Obviously, given a hash function with output size of n bits, if you try
messages, you'll get two of them with the same hash. The theory behnd birthday attacks tells us that for a n bit hash function we'd have to try out about
inputs to find a collision. That number is called the birthay bound.
Typical structure of a hash function
A hash function typically consists of a compression function which takes blocks of a fixed length as input and produced blocks of a fixed length (the output length of the hash function). Additionally, the output of the previous block is fed back to the input so that the next block depends in all the previous blocks. Otherwise, the hash function would be looking at the last block only 😉
Merkle-Damgard construction
The structure shown is known as the Merkle-Damgård construction, and most popular hash functions are based on this construction. However, alternative structures exist and many of the proposals for the SHA-3 contest are based on different constructions.
The SHA-2 family
Although MD5 and SHA-1 are way more popular, I decided to take a look and describe here the structure of the SHA-2 family of hash functions. The reason for this is that MD5 was broken a while ago, first by dr. Wang's team and later by a group of researchers including dr. Benne de Weger. I already talked about it here, although it's only in Spanish. You can see the hashcalc project's page if you don't read Spanish ;-).
Further, SHA-1 is very similar to MD5 and the same sort of problems usually apply to it. Therefore, I chose to look at the next family of hash functions, the SHA-2 family. This includes several hash functions with different output lengths: SHA-224, SHA-256, SHA-384, and SHA-512 where the number defines the number of output bits.
SHA-256 and SHA-512 use 32 and 64 bit words respectively, while SHA-224 and SHA-384 are just truncated versions of them. In the remaining of this section I'll explain SHA-256 since SHA-512's structure is basically the same but with different word size and initial values.
Bascially, the input message is divided in 512 bit blocks 
These 64 variables are processed with the compression function shown in this picture, where variables a..f are initialized according to the standard:
SHA-2 Compression function
After this processing, the intermediate hash value is computed as the addition (modulo 32) of the variables a..f and the previous intermediate hash value. This process is run for each message block and finally yields the message digest.
Of course, this is a very high level description of the algorithm. If you want to know the details, see the FIPS 180-2 standard publication.
The SHA-3 contest
Currently, an open contest is being held by the NIST to create a new hashing standard, SHA-3. Currently, the contest is in its second round and there are 14 second round candidates. The Second SHA-3 Candidate Conference is planned for August 2010 and the idea is to publish a revised Hash Function Standard by 2012.
More information on the contest and the submissions can be found in the NIST Hash competition website.
Crypto Series: Mifare Crypto1
Let's go back into Cryptography. This time I'll tell you how the (in)famous Crypto1 cipher works. It is used in the Mifare Classic RFID tags, typically used for building access control but also for many other systems such as the Oyster Card in London, the OV-Chipkaar in The Netherlands, etc.
We won't talk about the protocol details, nor about how the published attacks work. You'll find a couple of interesting links at the end though ;-).
Note: Images obtained from the papers linked at the end of the post.
The Crypto1 cipher
Crypto1 is a proprietary stream chiper from NXP found in the RFID tags from the Mifare Classic family. At first, it was studied by Karsten Nohl reverse engineering the chip itself. This information was published in the CCC 07, although not many details about the cipher were published.
In parallel, the Radboud Universiteit from Nijmegen was studying this kind of cards and with the help of the information published at CCC completely reverse engineered the cipher and published the details. Let's see how it works then...
My Hero Adventure (II) – How ‘to root’ your Android phone
In my previous post about the Hero I wrote about the structure of the system and commented how I got a root shell. In this post I'll tell you how to easily root your phone to be able to use applications that need root (admin/superuser) access in a VERY simple and easy way, without flashing recovery images or anything, just by installing an application and performing a click.
I tried it on my Hero with the latest HTC update, but it should work with any Android system with a kernel version up to 2.6.30.4. If you give it a try, give me feedback!
The application: Rooter
To assist myself in the rooting process I modified the FlashRec application by Christopher Lais, which uses an exploit for a NULL pointer dereference vulnerability in the Linux kernel (<= 2.6.30.4) in order to obtain backups of the flash memory and to flash new custom ROMs.
In my case, I removed most of FlashRec's code and only left there the stuff that was needed for my application: a couple of buttons and a TextView to show information about the result of the process.
Rooter
The Create rootshell button creates a setuid root shell in /system/bin/rootsh which you can use from the terminal, while the Extract SuperUser button extracts a Superuser.apk tool and an implementation of su to their respective directories. These applications are also from Christopher Lais I believe, and I didn't check their source code although I tried them out on the emulator and everything seems to be fine. As usual, all this comes without any warranty ;-).
From then on, an Intent (a message between Android's applications) will be sent to the Superuser.apk application each time a root request is performed using su. So, the user will be able to Allow once or always the requesting app. or to deny once or always.
Installing and running Rooter
Installing the application cannot be easier. Since I didn't upload it into the Market because I have no interest at all on doing so, you can download it from here and store it in your phone's SD card (I'm assuming you know how to ;-)). Once that's done, install a file manager if you don't have one yet. For instance Linda File Manager is available for free from the Market.
Using Linda File Manager, go to your SD card and find the Rooter.apk file. Clicking on it, choose to open it with Package Installer. At this point, it is possible that you need to enable the option to allow installation of apps from unknown sources in Settings > Application settings > Unknown sources.
Once enabled, accept and go back to Linda File Manager by pressing Back in your phone. Once there you can click again on Rooter.apk and now you will be able to install it. Once it's installed, press Open and the application will be launched. The only step left is to press Extract SuperUser and you'll have your Hero rooted. Now you can install applications that require root access such as Wifi theter :-).
Easy, isn't it?
Source code
For the curious reader, I've also uploaded the source code of the application here.
My Hero adventure (I)
So yes, I bought an HTC Hero a couple of weeks ago and I've been investigating it and looking around to see what's been happening in the android scene (let's call it this way 🙂 ). In this post I'm going to summarize what I discovered during my first days with the device... and will be followed by more updates because its edition is taking more time than I thought ;-).
First things first, the HTC Hero is a smartphone from HTC running a modified Android OS. It has a customized UI by HTC, multi-touch screen and browser with built-in flash support. Here is a small summary of the specifications:
- Processor: Qualcomm MSM7200A, 528 MHz
- Memory: 512 MB ROM and 288 MB RAM
- Quad-Band GSM/GPRS/EDGE and HSPA/WCDMA network connectivity
- GPS, Wi-Fi IEEE 802.11 b/g, Bluetooth
- Camera 5 Mpixel
- ...
Android development
Android provides a Java API for application development. Applications are normally implemented in Java, although it is possible to run ELF binaries compiled for ARM since it runs a Linux kernel. You can find all the documentation you need to start developing for the Android in http://developer.android.com/.
With the Hero, as with any other Android device I know of, you can enable USB debugging for development and use the tools in the Android SDK to connect to the device, upload applications and run them. Furthermore, the SDK provides an Eclipse plugin that makes it certainly easy to manage. You just press 'run as Android application' and it will run in your phone or in an emulator if no phone is connected.
However, the adb shell commands provides you a shell under the shell user and there is no way to get root.
Getting root shell access in my Hero
Didn't you say no way? Well... that's why it's written in italics ;-). Looking around I found references and howtos for rooting the Hero using the fastboot utility and flashing a recovery image into the phone. However I didn't have the sources used for creating this image so I decided to hold this for a while until I could actually look what was in there.
After some more reading, I also found the FlashRec utility which can be used to flash recovery images without having to reboot into flashboot mode and send it manually. And the source code was available! That sounds like a good oportunity to learn how things work in the Android world... so I downloaded the sources and started reading through them.
As it turns out, this FlashRec tool uses the sock_sendpage exploit for the Android, which sounds like fun ;-). So it includes an as_root binary which takes a template for a temporary file as its first argument, and then the command to be executed as root; when you press the 'flash' button, it just runs a flash_image binary included with Android but only executable for root.
But hey... do we really want to flash a recovery image? Well... it depends. In my case, I did because I wanted to install the new HTC Hero firmware update and I didn't have a handy Windows. But if that's not your case and you just want to obtain root, why don't you use this exploit to create a root shell?
You guessed it, that's what I did next :-). I just shrinked the FlashRec tool removing everything I didn't need, and made it execute a shell script that copied the /system/bin/sh shell into /system/bin/rootsh and gave it setuid root permissions. However, it took me quite a while to realize that there was no cp on this system! And it was because the ash shell it ships doesn't say Command not found when you type in cp as a non-privileged user, but Permission denied.
So my final script looked like this:
mount -o remount /dev/mtdblock3 /system
cat /system/bin/sh > /system/bin/rootsh
chmod 04755 /system/bin/rootsh
mount -o remount,ro /dev/mtdblock3 /system
exit 0
And after executing it I got the root shell waiting for me in /system/bin/rootsh. I only had to connect through adb and then run rootsh.
~ tuxed$ adb shell
* daemon not running. starting it now *
* daemon started successfully *
$ rootsh
#
Investigating the system structure
Well, we are in, now what? Let's take a look at the system structure: filesystems, shell, installed applications, etc. Let's start by running a mount to see what filesystems are there:
# mount
rootfs / rootfs ro 0 0
tmpfs /dev tmpfs rw,mode=755 0 0
devpts /dev/pts devpts rw,mode=600 0 0
proc /proc proc rw 0 0
sysfs /sys sysfs rw 0 0
tmpfs /sqlite_stmt_journals tmpfs rw,size=4096k 0 0
/dev/block/mtdblock3 /system yaffs2 ro 0 0
/dev/block/mtdblock5 /data yaffs2 rw,nosuid,nodev 0 0
/dev/block/mtdblock4 /cache yaffs2 rw,nosuid,nodev 0 0
/dev/block//vold/179:1 /sdcard vfat rw,dirsync,nosuid,nodev,noexec,uid=1000,gid=1000,fmask=0000,dmask=0000,allow_utime=0022,codepage=cp437,iocharset=iso8859-1,shortname=mixed,utf8 0 0
#
Ok, we can see a read-only filesystem mounted in the root directory ( using rootfs ), the usual /dev and /proc stuff and three partitions of the NAND flash mounted over /system , /data and /cache. The first one of them is mounted read-only and the latter are mounted with read-write permissions but suid files and devices are forbidden in there. Finally, our SD card is mounted under /sdcard as a FAT partition with read-write permission, and suid, devices and execution of binaries is forbidden from that partition.
Now, you are probably wondering... what about the missing partitions in the flash? Honestly, I didn't know either... one of them is for sure the recovery partition, which is where the code for recovering the device in case of problems (i.e. reflashing it) is stored. It helps to avoid bricked devices ;-). But how do we find out what is what?
What I did is first rebooting my hero, because the device was started a while ago and I wanted to see the complete boot log doing a simple dmesg. Then I did it, and scrolled up to find this:
<5>[ 4.765655] Creating 6 MTD partitions on "msm_nand":
<5>[ 4.766082] 0x024c0000-0x02500000 : "misc"
<5>[ 4.767425] 0x026c0000-0x02bc0000 : "recovery"
<5>[ 4.768890] 0x02bc0000-0x02e40000 : "boot"
<5>[ 4.770355] 0x02e40000-0x0d840000 : "system"
<5>[ 4.771820] 0x0d840000-0x15a40000 : "cache"
<5>[ 4.773162] 0x15a40000-0x20000000 : "userdata"
So we have 6 partitions in the NAND flash: misc, recovery, boot, system, cache and userdata. That makes for a 512 MB NAND flash memory, which matches the advertised size. Now, we have 3 of them mounted, one of them is identified as the recovery image and another one presumably conatins the boot loader. What is the "misc" partition then? Honestly, right now I have no clue but I guess we'll find out in a later post.
That's it for today. I'm stopping here because I feel that it's taking forever and I want to post this and move on for something else.
To be continued...
Status update
This is a quick note to give an update on my personal life and that kind of things ;-).
As some of you already know, I'll continue working in The Netherlands for one more year, until September 2010. The workplace will be the same, so I'll be working on smart cards and embedded devices, a little bit of Java programming and playing with interesting things such as fault injection (voltage/clock manipulation or laser radiation injection) and side channel analysis.
On the personal side (i.e. not work-related), at the end of June / beginning of July I went to Valencia for my summer holidays. I was at Campus Party, where I gave a presentation on smart card security and I worked together with Javi and Amin to achieve the first position of the security wargame organized by SbD.
Since then, I've been playing soccer quite a bit with the new team as well as going out more than I expected (partly due to the soccer team), being the case that most of my friends from last year did go back to Spain or were still on holiday.
On the other hand, I've both an HTC Hero smartphone, which is something I've been wanting to do for a while now. Actually, it's a quite nice device and I've been tinkering with it and trying to discover how it all works. This means you can expect a related post in a few days... but for now a small preview:
$ adb shell
$ rootsh
#
Yes, I already got root on the device based on some information I found out there ;-).
Finally, at the end of this week I'm going back home. First I'll go to Madrid, where I expect to gather with some of my Erasmus friends, some people from Wadalbertia and where I'll have my cousin's bachelor party. After this, I'll go to my village for the whole week... I'll try to schedule some post for you guys.
Linear Feedback Shift Registers (LFSRs)
In this post I'll provide a very simple description of linear feedback shift registers (LFSR for short). Further, we'll see how they are used to create stream ciphers. And all these things without going into mathematical details, for which I refer the interested reader to documents such as the Handbook of Applied Cryptography or this LFSR Reference.
Shift Registers
A shift register is basically a construction with interconnected several memory cells, where every cell stores one bit. So, the value of these cells conforms the so-called state of the register. When the register steps from one state to the next one (usually at each clock tick), the new state is created by simply shifting the bit in a cell to the cell next to it. Thus, the right-most bit goes out of the register, and a new bit goes into the left-most cell.
In this picture we can see an implementation of a 4 bit shift register:
Shift register
We can see an input line (Data in), 4 points where one can read the current state (Q1-Q4) and a clock input, which governs the register telling it in which moment it should step into the next state.
Linear Feedback Shift Registers (LFSRs)
Well, once you know what a shift register is, it is fairly straightforward to understand how a LFSR works. We just take the previous register and set the input as a linear combination of the different cells. Since there is a loop which feeds the register based on its previous state, we have feedback. Further, since this feedback is based on a linear function, then we have linear feedback, hence the name :).
LFSR
LFSRs' use in cryptography
So far, you probably have guessed that the main use of an LFSR in encryption systems is generating a series of pseudo-random bits to be used as a key stream in a stream cipher.
The idea is to generate a stream of bits with the minimum repetition possible, i.e. with maximal period. For its study, the connections in an LFSR are usually represented as a polynomial and the properties such a polynomial needs to meet to achieve maximal period are analyzed.
Basically, we need to get the LFSR to run through all its possible states before going back into the first one. So, if we have 16 bit registers, we'd want to have the LFSR pass through the 2^16-1 states before cycling back to the first one. And yes, I said 2^16-1 instead of 2^16 because the zero state should never appear. Otherwise the LFSR will never leave this state, since the feedback function is linear. For the curious readers, an LFSR will have maximal period if its generating polynomial is a so-called primitive polynomial (I'm pretty sure this name will ring a bell for some of you guys, although maybe not as a happy memory :P).
Setting aside the study of these polynomials, which involves somewhat comlex maths (to my non-mathematician opinion 😆 ), an LFSR by itself should not be used as a key stream generator because its properties make it fairly predictable. In fact, given an n bit LFSR, obtaining 2n bits of its output it is possible to recover the generating polynomial and be able to decrypt any subsequent text.
Therefore, LFSRs are not directly used in crypto, but they are generally used in one of these modes:
- Nonlinear combination of LFSRs: the output from several LFSRs is combined in a non-linear fashion to obtain a key stream.
- Nonlinear filter generator: the output is generated from a non-linear combination of the state.
- Clock-controlled generators: In this mode, several LFSRs step based on some rules, instead of stepping for every clock cycle.
With this kind of constructions it is possible to improve LFSR's properties for the creation of secure stream ciphers. And that's it for LFSRs from my side, for more information refer to these references:
Handbook of Applied Cryptography
Crypto Series: Introduction to stream ciphers
Today we're gonna step a little further in our Crypto series. We'll see the main properties of the so-called Stream Ciphers, how they work and some things that should be taken into account when they are used.
Later in this series, we'll see how Linear Feedback Shift Registes (LFSR) work and we'll see one of the most used stream ciphers, together with an example of wrong usage.
Keep on reading to learn more about this class of ciphers.
Back to life!
After being offline for almost the whole month of August, the server where this blog is hosted has misteriously become live today. I'm saying misteriously 'cause according to Javi it seems no one has powered it on, but it was just that the switches it's connected to were not online.
I'm sorry for the absence, you can expect to see new content from my side in a couple of days or so.