Amateur Cryptography Time

Hey /prog/, here's something I started a few months ago, and just found and improved upon some more recently. It's a hash function based an the XTEA block cipher. It's faster than MD5, though I can't attest to its security. I'm particularly concerned that short messages may be insecure, since it only uses four rounds (two cycles) of XTEA.

xtash.c

/*******************************************************************************
 * xtash.c -- a hash function based on XTEA.                                   *
 * Copyright (c) 2009, Samuel Fredrickson <kinghajj@gmail.com>;                 *
 * All rights reserved.                                                        *
 *                                                                             *
 * Redistribution and use in source and binary forms, with or without          *
 * modification, are permitted provided that the following conditions are met: *
 *     * Redistributions of source code must retain the above copyright        *
 *       notice, this list of conditions and the following disclaimer.         *
 *     * Redistributions in binary form must reproduce the above copyright     *
 *       notice, this list of conditions and the following disclaimer in the   *
 *       documentation and/or other materials provided with the distribution.  *
 *                                                                             *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER ``AS IS'' AND ANY EXPRESS *
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED           *
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE      *
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY        *
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES  *
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR          *
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER  *
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT          *
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY   *
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH *
 * DAMAGE.                                                                     *
 ******************************************************************************/

/*******************************************************************************
 * XTASH is a Merkle-Damgard construction hash function that uses XTEA as a    *
 * one-way compression function using the Davies-Meyer method. To speed things *
 * up, only two XTEA cycles are performed per compression, which probably      *
 * doesn't help with its security.                                             *
 *                                                                             *
 * Simple tests appear to show a good avalanche effect, but I don't reccommend *
 * anyone use this for anything serious, as I'm an amateur cryptographer.      *
 *                                                                             *
 * I've tested this on both big- and little-endian machines, and both provide  *
 * the same results. This code may run faster on a big-endian machine, because *
 * there's less swapping. However, since I'm using ntohl and htonl, swapping   *
 * should be faster on processors with a byteswap instruction.                 *
 *                                                                             *
 * Because XTEA operates on 64-bit blocks with a 128-bit key, the compression  *
 * function enciphers both halves of the previous state with the input message *
 * block.                                                                      *
 ******************************************************************************/

#include <netinet/in.h>
#include <stdlib.h>
#include <string.h>
#include "xtash.h"

/* Converts an array of 4 bytes into a 32-bit integer. */
static inline uint32_t UInt8s_To_UInt32(uint8_t in[4])
{
    return ntohl(*(uint32_t*)in);
}

/* Converts a 32-bit integer into an array of 4 bytes. */
static inline void UInt32_To_UInt8s(uint32_t in, uint8_t out[4])
{
    *(uint32_t*)out = htonl(in);
}

/* The XTEA encryption function. */
static inline void encipher(uint32_t v[2], uint32_t k[4])
{
    const static uint32_t XTEA_CYCLES = 2;
    uint32_t v0=v[0], v1=v[1], i;
    uint32_t sum = 0, delta = 0x9e3779b9;

    for(i = 0; i < XTEA_CYCLES; ++i) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum >> 11) & 3]);
    }

    v[0] = v0, v[1] = v1;
}

/* The XTASH compression function. */
static inline void compress(uint32_t a[4], uint32_t b[4])
{
    // just a simple compression function, but it seems to work decently.
    encipher(a, b);
    encipher(&a[2], b);
}

/* Converts the data to uint32_t, then calls compress(). */
static inline void compress_data(XTASH_State *state, uint8_t *data)
{
    uint32_t b[4];

    // construct a uint32_t block from the data.
    b[0] = UInt8s_To_UInt32(data);
    b[1] = UInt8s_To_UInt32(data + 4);
    b[2] = UInt8s_To_UInt32(data + 8);
    b[3] = UInt8s_To_UInt32(data + 12);
    // compress it.
    compress(state->state, b);
}

/* Initializes a hash state with the IV. */
void XTASH_Init (XTASH_State *state)
{
    // this is the md5 sum of "XTASH\n". probably not the best IV.
    const static uint32_t iv[4] =
        { 0x6a39cda1, 0x62a1c9dd, 0xf41a42cc, 0x28a638f4 };

    memcpy(state->state, iv, XTASH_DIGEST_SIZE);
    state->length   = 0;
    state->leftover = 0;
}

/* Updates the hash state with new data. */
void XTASH_Update(XTASH_State *state, uint8_t *data, uint64_t len)
{
    if(!len) return;

    state->length += len;

    // if there are leftovers,
    if(state->leftover) {
        // fill the rest of the leftover block as much as possible.
        while(len && state->leftover < XTASH_DIGEST_SIZE)
            state->data[state->leftover++] = *data++, len--;
        // if we're full of leftovers, use them and move on.
        if(state->leftover == XTASH_DIGEST_SIZE)
            compress_data(state, state->data), state->leftover = 0;
    }

    // while we have enough for one block,
    while(len >= XTASH_DIGEST_SIZE) {
        compress_data(state, data);
        len  -= XTASH_DIGEST_SIZE;
        data += XTASH_DIGEST_SIZE;
    }

    // if there are leftovers, save them.
    if(len) memcpy(state->data, data, (state->leftover = (uint8_t)len));
}

/* Finalizes a hash state into a digest. */
void XTASH_Final(XTASH_State *state, uint8_t *sum)
{
    uint32_t block[4];
    uint8_t fluff[XTASH_DIGEST_SIZE];

    // flush any leftovers.
    if(state->leftover) {
        memset(fluff, 0, XTASH_DIGEST_SIZE);
        XTASH_Update(state, fluff, XTASH_DIGEST_SIZE - state->leftover);
    }

    // create a block with the message length and compress it.
    block[0] = state->length & (~UINT32_MAX);
    block[1] = state->length & UINT32_MAX;
    block[2] = block[3] = 0;
    compress(state->state, block);

    // put state into the sum array.
    UInt32_To_UInt8s(state->state[0], sum);
    UInt32_To_UInt8s(state->state[1], sum + 4);
    UInt32_To_UInt8s(state->state[2], sum + 8);
    UInt32_To_UInt8s(state->state[3], sum + 12);
}

/* Streams data from a file and calculates the digest. */
void XTASH_Stream(FILE *f, uint8_t *digest)
{
    const size_t buffer_size = 4096;
    uint8_t buffer[buffer_size];
    XTASH_State state;
    size_t read;

    XTASH_Init(&state);

    while((read = fread(buffer, 1, buffer_size, f)))
        XTASH_Update(&state, buffer, read);

    XTASH_Final(&state, digest);
}

#ifdef XTASH_MAIN

int main()
{
    uint8_t digest[XTASH_DIGEST_SIZE];
    int i;

    XTASH_Stream(stdin, digest);

    for(i = 0; i < XTASH_DIGEST_SIZE; i++)
        printf("%02x", digest[i]);
    fputc('\n', stdout);

    return 0;
}

#endif

Now rewrite it in Java.

Ah, found an endianness issue!


diff --git a/xtash.c b/xtash.c
index 0c06dd7..632ca40 100644
--- a/xtash.c
+++ b/xtash.c
@@ -57,7 +57,7 @@ static inline uint32_t UInt8s_To_UInt32(uint8_t in[4])
 /* Converts a 32-bit integer into an array of 4 bytes. */
 static inline void UInt32_To_UInt8s(uint32_t in, uint8_t out[4])
 {
-    *(uint32_t*)out = htonl(in);
+    *(uint32_t*)out = ntohl(in);
 }

 /* The XTEA encryption function. */


>>2
Why?

Oh, by the way, here's the header file.

xtash.h

/*******************************************************************************
 * xtash.h -- a hash function based on XTEA.                                   *
 * Copyright (c) 2009, Samuel Fredrickson <kinghajj@gmail.com>;                 *
 * All rights reserved.                                                        *
 *                                                                             *
 * Redistribution and use in source and binary forms, with or without          *
 * modification, are permitted provided that the following conditions are met: *
 *     * Redistributions of source code must retain the above copyright        *
 *       notice, this list of conditions and the following disclaimer.         *
 *     * Redistributions in binary form must reproduce the above copyright     *
 *       notice, this list of conditions and the following disclaimer in the   *
 *       documentation and/or other materials provided with the distribution.  *
 *                                                                             *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER ``AS IS'' AND ANY EXPRESS *
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED           *
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE      *
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY        *
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES  *
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR          *
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER  *
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT          *
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY   *
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH *
 * DAMAGE.                                                                     *
 ******************************************************************************/

#ifndef _XTASH_H_
#define _XTASH_H_

#include <stdint.h>
#include <stdio.h>

#define XTASH_DIGEST_SIZE 16

typedef struct {
    uint32_t state[4];
    uint64_t length;
    uint8_t  data[XTASH_DIGEST_SIZE];
    uint8_t  leftover;
} XTASH_State;

void XTASH_Init   (XTASH_State *state);
void XTASH_Update (XTASH_State *state, uint8_t *data, uint64_t len);
void XTASH_Final  (XTASH_State *state, uint8_t *sum);
void XTASH_Stream (FILE *f, uint8_t *digest);

#endif

Not useing until Bruce posts about it on his blog.

I found an error on line 3, the last * appears to be too far to the right. Please add my name to the changelog.

I found a collision after 2 minutes of testing. LOL.

>>7
Post it then, faggot.

What does inline mean???

>>8
Find it yourself.

>>3
htonl is the correct function to use their.

"fjöldatala"

>>3
You found what?

>>6
It's a bug in Shiichan.

>>14
There are no bugs in Shiichan.

lol what

OP might take some notes from e.g. Schneier's Applied Cryptography and use something with a little more mixing like the first algorithm  from Table 18.1

H[i] = E<H[i-1]>(M[i]) ^ M[i]

where H[-1] is an IV arbitrary but fixed for the hash implementation, M[i] is the i'th block of data (encryption block size) to hash, and E<K> means encrypt under key K.  Padding like this (with MD  strengthening as per MD5) might help too:

void Final(Hash **pmd, byte digest[HASHSIZE], size_t length)
{
    Hash *md = *pmd;
    unsigned count = md->over;
    byte *p = md->in + count;

    /* there is always a free byte by construction */
    *p++ = 0x80;
    count = BLOCKSIZE - (count+1); /* free bytes in buffer */

    if(count<8) /* not enough space for the count */
    {
        memset(p,0,count);
        hash(md->buf, md->in); /*so hash zero filled block and start again*/
        memset(md->in, 0, BLOCKSIZE-8);
    }
    else memset(p, 0, count-8);

    /* pack high byte first where bits = number of bytes hashed << 3, encoded as a big-endian 64-bit integer */
    md->in[4] = (byte)((md->bits[1] >> 24) & 0xFF);
    md->in[5] = (byte)((md->bits[1] >> 16) & 0xFF);
    md->in[6] = (byte)((md->bits[1] >> 8) & 0xFF);
    md->in[7] = (byte)((md->bits[1] ) & 0xFF);

    md->in[8] = (byte)((md->bits[0] >> 24) & 0xFF);
    md->in[9] = (byte)((md->bits[0] >> 16) & 0xFF);
    md->in[10]= (byte)((md->bits[0] >> 8) & 0xFF);
    md->in[11]= (byte)((md->bits[0] ) & 0xFF);

    hash(md->buf, md->in);
    memcpy(digest, md->buf, HASHSIZE);
}

>>11
I thought so when I wrote it, too, but when I tested on my old PPC Mac that hash it produced for a message didn't match what my PC produced. After I changed it, the Mac produced the same hash as the PC.

>>13
Read up on little- and big-endian design.

>>17
Yeah, I should definitely buy that book.

>>7
Yeah, post it, faggot.

>>6
No.

>>5
I'd be so honored if I was mentioned by Bruce.

>>18¶1
You suck at testing.  The calls are identical on x86 and no-ops on ppc.

>>19


/* Converts an array of 4 bytes into a 32-bit integer. */
static inline uint32_t UInt8s_To_UInt32(uint8_t in[4])
{
    return ntohl(*(uint32_t*)in);
}

This takes a number stored in big-endian order in an array and converts it to a number. On little-endian systems, this involves a byte swap; on big-endian, it is a no-op.


/* Converts a 32-bit integer into an array of 4 bytes. */
static inline void UInt32_To_UInt8s(uint32_t in, uint8_t out[4])
{
    *(uint32_t*)out = ntohl(in);
}

This code takes a number and, on little-endian systems, performs a byte swap on it, and then puts those bytes in order into an array.

Here's the annotated assembly version of the functions in x86.


UInt32_To_UInt8s:
    bswap %edi           # swap "in" to be big-endian.
    movl    %edi, (%rsi) # load by into the array.
    ret

UInt8s_To_UInt32:
    movl    (%rdi), %eax # load big-endian "in" into reg
    bswap %eax           # swap bytes to make little-endian.
    ret                  # return the result.

Here's my hashing /prog/ram.

#include <stdio.h>
#include <stdlib.h>

int main(int argc,char* argv[]){
    int n=0;
    char c=1;
    while((c=getchar())!=EOF) n+=c;
    printf("%c",n%255);
    return 0;
}

>>21
one byte checksum?

>>21
Change char c=1; to unsigned char c=223; -- unsigned is faster, and prime numbers are more secure.

Also you should probably output hexadecimal; it's easier to work with.

It's funny because >>1 and >>17 actually have no clue about cryptography but they make cool hash functions in their spare time because cryptography is so elite. In conclusion, if you want to be a script kiddie, write lots of stuff relating to cryptography.

>>24
But I never claim to know much about cryptography. "Simple tests appear to show a good avalanche effect, but I don't recommend anyone use this for anything serious, as I'm an amateur cryptographer." I'd never release a cryptographic algorithm with the arrogance to think that it's well-tested and proven.

But I'd like to think I know at least something about cryptography, which I've learned mostly by browsing various Wikipedia articles. I wrote XTASH just because it was something to do, but that I hadn'd seen done: turn XTEA into a hash algorithm. I've learned that any block cipher can be turned into a hash function, and that the Merkle-Damgard construction is provably secure so long as the compression function is proven secure. I have a feeling that XTASH's compression function leaks information about its inputs, especially for small messages.

>>25
None of what you said invalidates any of >>24.

Thank you, Samuel.

>>25
compression function leaks information
Oh, you mean like- every compression function ever to have existed and that will ever exist?

>>28 doesn't know anything about basic cryptography.

>>29 doesn't know anything about advanced cyptography.

bitches dont know about my advanced cryptography

hello im [b]Bruce[/i] the cryptographer join my community of cryptographers if you payme enough i will give you access to a private area of block ciphers ;)

>>33
What are you resurrecting my old shit for? GTFO.

The notion of cardinality, as now understood, was formulated by Georg Cantor, the originator of set theory, in 1874–1884. Cardinality can be used to compare an aspect of finite sets; e.g. the sets {1,2,3} and {4,5,6} are not equal, but have the same cardinality, namely three (this is established by the existence of a one-to-one correspondence between the two sets; e.g. {1->4, 2->5, 3->6}).