#!/usr/bin/perl
#
# implementation of the ORYX stream cipher
# used to encrypt data sent to and from cell phones.
# 
# additionally, an attack is implemented which is
# able to recover the key in < 2**20 (12 * (65536 + 6144 + 576 + 51 + l))
# where there's a 96-bit key

use strict;
my (%L, @X, @A, @B, @K);

# produce permutation L
my $j = 0;
while (<DATA>)
{
	my @row = split(/\s+/, $_);
	for (my $i = 0; $i < @row; $i++)
	{
		$L{unpack("h", chr($j)) . unpack("h", chr($i))} = $row[$i];
	}
	$j++;
}

# our three 32-bit keys to produce a 96-bit key
@X = h2b("deadbeef");
@A = h2b("01234567");
@B = h2b("76543210");
print "X: " . b2h(@X) . "\n";
print "A: " . b2h(@A) . "\n";
print "B: " . b2h(@B) . "\n";

foreach (1 .. 100)
{
	push @K, iterate();
}
print "K: @K\n";


# attack time
print "\nAttack!\n";
my @C = @K;

# lose our "info"
@X = @A = @B = ();
@K = @K[0..24]; # we know 25 keystream bytes

# extensions of A and B
my @e = (
	["0", "0"],
	["0", "1"],
	["1", "0"],
	["1", "1"],
	["1", "00"],
	["1", "01"],
	["1", "10"],
	["1", "11"],
	["0", "00"],
	["0", "01"],
	["0", "10"],
	["0", "11"],
);

# guess H(A) and H(B) (we will exhaust this space, which is only 2**16)
# for each keystream byte
my $X = ($K[0] - L(H(@A)) - L(H(@B))) % 256;
foreach my $i (1 .. 25)
{
	# brute force H(A) and H(B) (2 ** 8 each)
	foreach my $ab (0 .. 2 ** 16)
	{
		my @T;
		my ($A, $B) = unpack("CC", pack("n", $ab));

		# next fills
		$T[0] = [ split(//, "0", unpack("B7", $X)) ];
		$T[1] = [ split(//, "1", unpack("B7", $X)) ];
		
		foreach my $j (0 .. 1)
		{
			$T[$X] = [ split(//, unpack("B8", pack("s", ($K[$i] - L(H($e[$j][0])) - L(H($e[$j][1]))) % 256 ))) ];
#print "X=$X T[X]=$T[$X] H(T[0])=" . H(@{$T[0]}) . " H(T[1])=" . H(@{$T[1]}) . "\n";
			if (ord(pack("B8", @{$T[$X]})) == H(@{$T[0]}))
			{
				print "sweet $T[0] 0 - $e[$j][0] $e[$j][1] ($j)\n";
			}
			if (ord(pack("B8", @{$T[$X]})) == H(@{$T[1]}))
			{
				print "sweet $T[1] 0 - $e[$j][0] $e[$j][1] ($j)\n";
			}
		}
	}
}

sub iterate
{
	fx();
	fa();
	fb();
	fb() if $X[26];
	return ((H(@X) + L(H(@A)) + L(H(@B))) % 256);
}

sub fx
{
	my $Y = pxor(\@X, 0, 4, 5, 8, 9, 10, 13, 15, 17, 18, 27, 31);
	$X[$_] = $X[$_-1] for reverse(1 .. 31);
	$X[0] = $Y;
}
sub fa
{
	my $Y = $X[29] ?
		pxor(\@A, 0, 1, 6, 7, 8, 9, 10, 12, 16, 21, 22, 23, 24, 25, 26, 31) :
		pxor(\@A, 0, 1, 3, 4, 6, 7, 9, 10, 11, 15, 21, 22, 25, 31);
	$A[$_] = $A[$_-1] for reverse(1 .. 31);
	$A[0] = $Y;
}
sub fb
{
	my $Y = pxor(\@B, 0, 2, 5, 14, 15, 19, 20, 30, 31);
	$B[$_] = $B[$_-1] for reverse(1 .. 31);
	$B[0] = $Y;
}

# xor multiple bits together
sub pxor
{
	my $reg = shift;
	my $bit = $reg->[shift()];
	for (@_)
	{
		$bit ^= $reg->[$_];
	}
	return $bit;
}

# return high byte helper function
sub H
{
	return ord(pack("B8", join("", @_[-8..-1])));
}

# L is a known permutation of {0..255} (see DATA)
sub L
{
	return ord(pack("H2", $L{unpack("H2", chr($_[0]))}));
}

# hex to bin helper function
sub h2b
{
	my $hex = shift;
	my $bin;

	while (my $tmp = substr($hex, -2, 2, undef))
	{
		$bin = unpack("B8", pack("H2", $tmp)) . $bin;
	}

	return map int($_), split(//, $bin);
}

# bin to hex helper function
sub b2h
{
	return unpack("H8", pack("B32", join("", @_)));
}

__DATA__
ed 3e 0d 20 a9 c3 36 75 4c 2c 57 a3 00 ae 31 0f 
19 4d 44 a0 11 56 18 66 09 69 6e 3d 25 9c db 3f 
65 58 1a 6d ff d7 46 b3 b1 2b 78 cf be 26 42 2f 
d8 d4 8e 48 05 b9 34 43 de 68 5a aa 9d bd 84 a2 
3c 50 ce 8b c5 d0 a5 77 1f 12 6b c2 b5 e6 ab 54 
81 22 9f bb 5c a8 dc ec 2d 1e ee d6 6c 5f 9a fd 
c8 d5 94 fc 0c 1c 96 4f f9 51 da 9b df e1 47 37 
d1 eb af f7 a4 03 f0 c7 60 e4 f4 b4 85 f6 62 04 
71 87 ea 17 99 1d 3a 15 52 0a 07 35 e0 70 b6 fa 
cb b0 86 a6 92 fb 98 55 06 4b 5d 4a 45 83 bf 16 
7c 10 95 28 38 82 f3 6a f8 fe 79 39 27 2a 5e e7 
59 b8 1b ca 8d d3 7b 30 33 90 d2 d9 ac 76 8f 5b 
a7 0e 63 c4 b2 e9 97 91 53 7a 0b 41 08 c1 8c 7d 
88 24 f5 f2 01 72 e8 80 49 13 23 9e c6 14 73 ad 
8a 29 ef e5 67 61 ba e2 7e 89 64 02 c0 21 6f f1
dd b7 c9 e3 cd 3b 93 2e 40 bc 4e a1 cc 74 32 7f