Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

for my hobby tinkering project, I need a mixing function that takes 32-bit input and has 32-bit output (and will, most likely, run in a 32-bit C environment) and the following property (independent of endianness, i.e. it’s enough to only look at either big endian or little endian (or pdp endian) systems):

union u {
    uint32_t u32;
    uint8_t u8[4];
} ival, oval, ival2, oval2;
int x;

ival.u32 = /* some unsigned 32-bit value */;
oval.u32 = ƒ(ival.u32);

x = /* some value ∈ { 0, 1, 2, 3 } */;
ival2.u32 = ival.u32;
ival2.u8[x] ^= /* some nonzero octet */;
/* ival2 = ival where exactly one input octet differs */
oval2.u32 = ƒ(ival2.u32);
assert(oval2.u8[0] ≠ oval.u8[0]); /* first output octet differs */
assert(oval2.u8[1] ≠ oval.u8[1]); /* second output octet differs */
assert(oval2.u8[2] ≠ oval.u8[2]); /* third output octet differs */
assert(oval2.u8[3] ≠ oval.u8[3]); /* fourth output octet differs */

That is, I need a function where, when you change one of the octets in the input, all four octets of the output differ.

Since this is a 32-bit to 32-bit mapping, it can be a perfect mixing function (bijective, not one-way); this would be extremely beneficial because I could then replace the Final function of a 32-bit (nōn-cryptographic) hash (based on Jenkins’ one-at-a-time but tweaked) I’m using in the same context with it, too, and it would not lose any fractional bits of entropy from the input.

Of course I could do this “the simple way” with lookup tables, but the idea is to have this in only a few lines of code (that is, few machine instructions), either completely algorithmic, or with only, say, up to 256 bytes of read-only data. I bet there’s something like this already around. (My target CPUs are, for now, i486, sparc v8, 32-bit MIPS, but I’d want it in portable code, not assembly; C is just fine as long as it uses only unsigned integers, since I’ll most likely need to implement it in C.)

Please only include code snippets if they are true Public Domain (e.g. government work) or I can reuse them under the MIT Licence, the MirOS Licence, or the BSD Licence, or in a language not C with a permission for me to “rewrite the same algorithm” in C (while not copying a line of code); otherwise, please only include algorithmic descriptions that are enough for me to write C code from it. And nothing that’s legally dangerous or questionable of course ☺

My strength is coding, not mathematics (I already had to prove the bijectivity of the Finish function of my modified Jenkins-OAAT empirically, i.e. by trying all possible 2³² combinations), that’s why I thought to ask here. (No homework or commercial stuff, just trying to improve the world, in the context of the BSD Unix operating systems, and Open Source.)

share|improve this question
    
The avalanche property does not have to hold if more than one octet gets modified, right? –  orlp Dec 5 '13 at 23:31
    
Oh, sorry, that is underspecified then. If two get modified, the other two should both change; similar for three, but this is harder to express. I think that, since we get a 2³²→2³² mapping, this should be doable. –  mirabilos Dec 5 '13 at 23:42

2 Answers 2

up vote 3 down vote accepted

At first glance, the MixColumn step from AES (actually, a single column of that transform) sounds like precisely what you're looking for. It is invertable (AES depends on that), and it does have the property that if one input octet changes, then all four output octets are guaranteed to change.

Most commonly, it's done by table lookup; however there's no reason it couldn't be done by inline code (and that inline code ought to fit in 256 bytes).

share|improve this answer
    
Hm, if the table is small enough that would work (speed is not unimportant either). I glanced at it too and it does seem to fit; I’ll look at it in more detail probably on the weekend, but thanks already! –  mirabilos Dec 5 '13 at 23:45
    
@mirabilos If mind-blowing speed is not crucial a table-less implementation is very easy. –  orlp Dec 5 '13 at 23:45
    
OK, thanks. Easy maybe but not from the description on Wikipedia ;-) I’ve got AES code in the source tree already though, so I know where to look. Thanks! –  mirabilos Dec 5 '13 at 23:47
1  
@mirabilos Don't bother - I'm way too nice: gist.github.com/nightcracker/7816269 –  orlp Dec 5 '13 at 23:49
    
Woah, thanks! I’ll still look at it when I get some more time, since I’ll be running a number of empirical tests on it (got access to a machine with 64 GiB RAM at work :D which is kinda useful for this “big data” thing). –  mirabilos Dec 6 '13 at 0:08

There is such a function, called qht(), in some of my work. For the whole context, see: ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/

Here's the central bit of code & comment:

/*
Quasi-Hadamard transform
My own invention

Goal is to mix a 32-bit object
so that each output bit depends
on every input bit

Underlying primitive is IDEA
multiplication which mixes
a pair of 16-bit objects 

This is analogous to the
pseudo-Hadamard transform
(PHT) originally from the
SAFER cipher, later in
Twofish and others

Conceptually, a two-way PHT
on a,b is:

x = a + b
y = a + 2b
a = x
b = y

This is reversible; it loses
no information. Each output
word depends on both inputs.

A PHT can be implemented as

a += b
b += a

which is faster and avoids
using intermediate variables

QHT is the same thing using
IDEA multiplication instead
of addition, calculating a*b
and a*b^2 instead of a+b and
a+2b

IDEA multiplication operates
on 16-bit chunks and makes
every output bit depend on
all input bits. Therefore
QHT is close to an ideal
mixer for 32-bit words.
*/
u32 qht(u32 x)  
{  
    u32 a, b ;  
    a = x >> 16 ;       // high 16 bits  
    b = x & 0xffff ;    // low 16  
    a = idea(a,b) ;     // a *= b  
    b = idea(a,b) ;     // b *= a  
    return( (a<<16) | b) ;  
}  
share|improve this answer
    
Sorry, this is not appropriate, this has totally bad avalanche. But thanks for trying. –  mirabilos Nov 8 at 22:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.