CaCert is a Certification Authority that works with a web of trust: people meet and assure (similar to keysigning) eachother. If you’ve been assured by enough people you’ll be able to let your ssl server key be certified by cacert. It’s a lot more secure than other CA’s who just give anyone a certificate who pays enough.

Still a hierarchical system with a CA is flawed. When the CA is compromised, the whole system fails. PGP’s web of trust hasn’t got this weakness.

(Got a nice shiny cacert certified ssl certificate on my webserver now)

“Nothing to hide”

In this short essay, written for a symposium in the San Diego Law Review, Professor Daniel Solove examines the “nothing to hide” argument. When asked about government surveillance and data mining, many people respond by declaring: “I’ve got nothing to hide.” According to the “nothing to hide” argument, there is no threat to privacy unless the government uncovers unlawful activity, in which case a person has no legitimate justification to claim that it remain private. The “nothing to hide” argument and its variants are quite prevalent, and thus are worth addressing. In this essay, Solove critiques the “nothing to hide” argument and exposes its faulty underpinnings.

“I’ve Got Nothing to Hide” and Other Misunderstandings of Privacy

Not only is its subject very relevant, the Essay is very well written and a pleasure to read.


Don’t use md5(microtime()). You might think it’s more secure than md5(rand()), but it isn’t.

With a decent amount of tries and a method of syncing (like a clock on your website) one can predict the result of microtime() to the millisecond. This only leaves about a 1000 different possible return values for microtime() to be guessed. That isn’t safe.

Just stick with md5(rand()), and if you’re lucky and rand() is backed by /dev/random you won’t even need the md5(). In both cases it will be quite a lot more secure than using microtime().

Simple Branch Prediction Analysis

This paper outlines simple branch prediction analysis attack against the RSA decryption algorithm.

At the core of RSA decryption is a loop over all bits of the secret key number d. When the bit 1 there is other code executed than when the bit is 0. The CPU branches on a different bit.

A spy process can be run on the CPU which measures the branch cache of the CPU by flooding the cache with branches and measuring the time it takes. When the sequentially running secret process doing RSA decryption makes a different branch (1 instead of 0) it can be noticed in a change of execution time on the spy process’s branches.

In this way quite a lot of secret bits can be derived.

There are some clear buts:

  • You must be able to insert a spy process on the computer itself and it should know exactly when the RSA process runs.
  • To attain clear readings, there shouldn’t be other processes claiming too much CPU time.
  • The spy and CPU process should run on the same physical processor and preferably at the same time (dual core)

An easy fix would be to allocate a whole processor for the RSA decryption time, so no process can spy. Another option would be to add noise in the Branch Prediction Buffer, but that would result in a performance loss.

DDOS on Hash Tables (Self Balancing Hash Tables)

Hash Tables are widely used in server software. A malicious user can easily forge keys in the communication with the server that will result in hashes from the keys so that they will end up in the same bucket. This will force the hashtable to grow each time this bucket is filled.

In a worst case implementation, this will result in an enormous amount of empty buckets and only one full bucket. Even if the implementation is smart and will therefore only will grow the targetted bucket, the hash table will fail its use. The hash table is meant to make lookups for a key fast by distributing the pairs in buckets, this effect is gone when all pairs are located in one bucket, which will cause linear time look-ups.

One malicious user won’t be able to crash a server, but a DDOS attack with several users would be tremendously more efficient when targeting this weakness in hash tables.

A simple solution would be to randomly pick a salt for the hash function on each new instance of a hash table. Basically we prefix each key with a random salt before we hash it. The malicious user might know the hash function, but he has to guess the salt, which neglects the effect.

Additionally logic could be added to detect an unbalanced hash table and switch the salt on when the table is unbalanced.

This could also be usefull to balance hash tables when there is no malicious user, but the keys are possibly unfortunate.

Rainbow Tables: Coverage

A rainbow table is generated by creating (m) chains using randomly picked starting keys. The reduction functions result (or ought to result at least) in evenly distributed new keys. Their is only a probability that a certain key/cipher pair is in the table.

I’ll gradually explain how the coverage can be calculated.

Take m chains, each 1 long to cover a keyspace of N keys. The chance that you can find the key is:

[tex]\displaystyle P = \frac{m}{N}[/tex]

When we have 1/2N chains, we’ll subsequently have a P of 1/2, a 50% coverage. Obvious.

When each chain would be 2 in length it gets trickier.

[tex]P = \frac{m}{N}[/tex] still is the chance that we can find the key in the first column (first item of each chain of the table) of the table. The second column isn’t as straight forward. We’ve blindly assumed that each key in the first column is unique, which is true for the first column, but certainly isn’t for the second column. A few chains can merge. The second column is ‘random’.

The chance that a certain key is in a specific chain of the second column is [tex]\frac{1}{N}[/tex]. The chance that a certain key is in the second column is [tex]1 – \left(1 – \frac{1}{N} \right)^m[/tex] (One minus the chance that there isn’t a certain key in a certain chain multiplied by itself the-amount-of-chains times).

The amount of keys covered by this column is the chance that a certain key is in the column times the amount of keys: [tex]N \left(1 – \left(1 – \frac{1}{N} \right)^m \right)[/tex].

The chance a certain key is in any of the two columns would be:

[tex]\left( \frac{m}{N} \right) \cdot N \left(1 – \left(1 – \frac{1}{N} \right)^m \right) \over N[/tex]

The third column’s coverage can be calculated by taking the unique keys in the second column as m was taken for the amount of unique keys for the first column. With each chain t in length this formula applies:

[tex]\displaystyle m_1=m \\ m_{n+1}=N \left( 1 – \left( 1 – \frac {1}{N} \right) \right) \\ P=1-\prod^m_{i=1}1-\frac{m_i}{N}[/tex]

Reversing CRC

Cyclic Redundancy Code

CRC is a hash which is frequently used as a checksum for data in for instance archives. Who hasn’t had bad CRC errors once when opening corrupted zips. CRC is a very old algorithm and over time it changed a lot from the original idea.

The original idea behind CRC was representing the data that you wanted the hash from as a big number and dividing it by a certain number called the polynomial and taking the remainder of the division as the hash. For instance: 23 % 3 = 2 (% is the modulus operator, which is the remainder of a division)

The initial problem was that dividing is a rather intensive operation. They wanted to simplify CRC to make it easier to implement in hardware and make it faster. They did this by getting rid of the carry used in the substraction of the division:

Normal substraction (binary): 10101 - 01100 = 01001
Without carry: 10101 - 01100 = 11001

Substraction without a carry is basicly a eXclusive bitwise OR (XOR), which returns only 1 when one of the operands is 1 and the other 0.

The algorithm required was faster bit still worked bit by bit, which isn’t really what a computer likes. A computer works best with one to four bytes. To make CRC faster they cached 8 operations at the time by precomputing the results for a certain start value and put it in a table called a XOR Table.

The required code for the CRC calculation itself now became very simple:

hash = (hash >> 8 ) ^ table[data ^ (0xff & hash)]

They changed the CRC algorithm once more by making it reflected. This means that the input data is reversed bitwise: 011101011 <-> 110101110. This was done because most of the hardware chips at the time reversed data bitwise. For it was too much work to reflect each byte of incoming data they changed the algorithm that generates the Crc table to create a table which has the effect of reflected data.

This is by the way not totally correct; the result still was different for a reflected than a non-reflected algorithm for they wouldn’t cache the whole piece of data to reverse it but did it per byte at calculation.

At this moment CRC barely resembles the original idea of a modulus.

Reversing CRC

First off, credits for the original idea of CRC patching go to anarchriz.

CRC is a cryptographicly very weak algorithm. It can be easily reversed for it has got the property that with 4 bytes you append to the current computed hash you can get every required hash. You can change the whole message and add 4 patch bytes to patch the hash to the one you like.

The ability to patch a CRC also makes it possible to very efficiently generate all possible source data of a checksum. Although it still is a bruteforce method you got 4 bytes freely and patching is faster than calculating.

Patching is basicly going back the way CRC works. Crc basicly takes the hash, moves it 1 byte to the right (dropping one byte) and xor-ring it with the table entry. The nice thing about normal CRC is that the first byte of a table entry is unique for that entry.

For the first byte of the entry is unique for that entry and it is put in the hash xor-red with 0 for that is what is shifted in from the right you can work back the whole entry used.

For instance:

My is: 0x012345678, this means that it was xorred with the entry in the CRC table that starts with 0x12. When you xor the hash with that full entry the only thing that the next byte was xorred with was the start of a table entry too.

When reversing the current hash you know what will be xorred on the patch you’ll give. Xorring this with your wanted hash is enough.

The resulting algorithm is suprisingly simple:

– Put the current hash byte wise reversed at the start of a buffer. Put the wanted hash byte wise reversed at the end of the current hash in the same buffer.
– Look up the entry in the table that starts with byte 7 in the buffer. Xor this value of position 4, and Xor the entry number on position 3. Repeat this 4 times with the positions each time one decremented. (thus 7,6,5,4 and 4,3,2,1 and 3,2,1,0)

When you’ve done this the required patch bytes are the first 4 bytes in the buffer.

Some Crc variants tend to use duplicates in the crc-table which means there could be more than one original table entry used. You should just branch and try all of them.

I’ve made a simple python script to work with crc32 and to patch a hash.

You can download it Here. And there is a C implementation here.

Update Fixed a bug in the example.

Update Andrea Pannitti wrote an implementation in java.

Update I found a great article by Stigge, Pl�tz, M�ller and Redlich about reversing CRC. They pretty much nailed it by bringing it down to elementary algebra. They explain an algorithm which is able to patch data at any given point to adjust the CRC to any desired value.

Linux Mount Security

With the linux Set UID Attribute you can let the owner of the file be the one the execute it when another user executes the file. This feature has traditionaly be used for system tools in linux which require root access to run but also must be able to be run my users.

It came to mind that a floppy with the ext2 filesystem could contain files of the root user with this Set UID Attribute set. Which theoraticly would allow anyone who is allowed to mount floppy’s or other media with an filesystem that supports this attribute to gain root access for a program.

On my system I got this entry in my /mnt/fstab, which allows an user to mount the floppy:

/dev/floppy/0 /mnt/floppy auto noauto,user 0 0

I made a simple C program which would show the contents of /etc/shadow, which contains the password hashes of the users, and chmodded it accordingly. (chmod = showshadow; chmod go+x showshadow; chmod u+rs showshadow)

I ran my program, and it seemed to work! The contents of the /etc/shadow file was streaming on my console.

Euforicly I went to another linux computer and tried the same trick.

darkshines@darkshines-one /mnt/floppy $ ./showshadow
bash: ./showshadow: Permission denied

Dissapointed but releived it seemed that linux had already some precaution against a root Set UID-ed executable.

I copied the contents of the folder whilest preserving permissions to another folder outside the /mnt/floppy and it all seemed to work again, although I couldn’t do it with a normal user account for I can’t preserve the owner when copying a file as a normal user.

I wondered how linux would secure it and tried to run the program while it was unchmodded.

darkshines@darkshines-one /mnt/floppy $ ./showshadow.unchmodded
bash: ./showshadow.unchmodded: Permission denied

The warning is from bash which can’t seem to execute the program. (note that it isn’t the program that can’t acces shadow) . After recompiling it on the floppy itself it seems that linux prevents any program to be executed in an user mounted folder.

I recon that that security precaution is a bit too strict. Although copying the file from the medium to a normal folder and then executing is still possible, I find it a bit strange that nothing of the user itself can be executed.

This could result in trouble when dealing with netmounts where one user can has a share on a server where he puts his files and can access only that mount for space on a terminal, when dealing with an user mount which would be required for security.

Safe web authentication

The major problem with security of web applications is that the client sends the login name and password in plain text if https isn’t available. A nasty person with access to the network could use ARP poisening alongside packet sniffing to acquire the login, which wouldn’t really be desirable.

I stumbled accross a very interesting piece javascript which implements the md5 hash algorithm:

Using a hash makes it impossible to reverse engineer a password and makes authentication safer. An issue with this is that you only require the hash, not the password to get in. To prevent this the password should be salted before hashed.

Basicly a secure authentication via http would look like this:

Client sends request for login to server.
Server sends the login form which includes a login id and salt to the client.
Server stores the login id and salt it sent to the client.
Client sends the hash of the filled out password and received hash alongside the login id from the server to the server.
Server checks whether the hash of the password in the database and the received hash combined with the login id are valid.
Server sends whether authentication was a success.

Maybe I’ll implement an example application :-). In any case I hope that this will be employed.

Update, most authentication system used by webbased software are still vulnerable and would almost neglect the use of this by being able to hijack a session by just getting the session key. The client however could also implement javascript to use a similar method with a salt to protect the session key. The problem still is that it is extra overhead on the client and that not every client has got javascript enabled.

Copy protecting

From software, audio to video are being illegaly copied and everytime the major brands try to implement some kind of protection. They always claim their protection to be perfect, and yet it is always broken, for it is quite simple:

As long as the intended user has the platform on which he`ll run it in his own possession he can always adapt it in someway to extract the data. Even the best video protection can’t beat making a bypass in your monitor to acquire the image on your screen.

Even protecting something like a DVD is almost impossible. The dvd player hardware and software must be able to read what’s on the cd, and a protection must be able to be read to. Also there must be dvd writers to write a protection. Now all major brands can say they’ll put a protection in their DVD burners to protect from writing to the DVD protection section, but then another brand creates their DVD burners that can write to it and everyone will buy those which the big brands won’t let happen. And even if they got the disk itself truly protected someone can emulate the DVD using software or even hardware.

Also there are things that allow itself to be copied, but the original copier can be tracked; this by putting in every video/song/software a unique signature which can be tracked back to the store which then can track it back to the person who copied it. Sounds great, would be impossible to forge when they use strong RSA like cryptography, just one problem, when inserting random trash instead of the signature someone can know the piece is illegal but cannot track someone, hopeless.

The only, and only way, to stop illegal copying is making buying legaly less of an effort than acquiring illegaly. I hope they will relize this sooner or later for honoustly I`m becoming sick of all those ‘magic’ protections.

PHP Security Consortium

The PHPSC is a site managing a lot of resources on PHP security.

For all those starting or sometimes using PHP this is a must read.

Also I’d advice for people who want to know whether there site is safe enough is to try to play the other site by trying out hacking yourself: It is easier than you might have thought.