#!/usr/bin/perl
#
# implementation of RC4 cracking, given the first byte of plaintext + IV
# expects input like:
# IV: 254 130 35 - cipher: 21a90f203a66763f33
#
# example usage:
#
#   >  perl rc4-generate.pl deadbeef 5000 | perl rc4-crack.pl P
#
# with 5000 packets, we should get the key 50% of the time
# due to the birthday paradox. happy birthday to me.
#
# -samy kamkar, code@samy.pl

use strict;

die "usage: $0 <first plaintext byte>\n" unless @ARGV;
my $byte = ord(shift);
my (@S, @key);
my %crack;
my ($i, $j, $k, $acquired) = (0, 0, 0, 0);
my $ivs;

my %IVs;
while (<STDIN>)
{
	$ivs++;
	my (undef, $IV1, $IV2, $IV3, undef, undef, $c) = split;
	push @{$IVs{$IV1}}, [ $IV2, $IV3, (hex(substr($c, 0, 2)) ^ $byte) ];
}

while (1)
{
	# only look at the IVs that help us here
	foreach (@{$IVs{$acquired+3}})
	{
		my ($IV1, $IV2, $IV3, $c) = ($acquired + 3, @{$_});

		# initialize what we know
		$j = $i = 0;
		@S = (0 .. 255);
		my @K = ($IV1, $IV2, $IV3, @key);
		for $i (0 .. 2 + $acquired)
		{
			$j = ($j + $S[$i] + $K[$i]) % 256;
			($S[$i], $S[$j]) = ($S[$j], $S[$i]);
		}

		# obtain S[3]
		if ($S[1] < $acquired + 3 && $S[1] + $S[$S[1]] == $acquired + 3)
		{
			$crack{($c - $j - $S[$acquired+3]) % 256}++;
		}
	}

	# find our most likely key
	my ($c, $count, $k);
	foreach my $crack (keys %crack)
	{
		if ($crack{$crack} >= $count)
		{
			$k = $crack;
			$count = $crack{$crack};
		}
		$c += $crack{$crack};
	}
	%crack = ();

	# add to key if > 4% hit
	if ($c && $count / $c >= 0.03 && $c / $ivs >= 0.03)
	{
		$key[$acquired++] = $k;
		print "Acquired " . unpack("H2", chr($k)) . " [$k] - $count/$c recovered (" . int(100*($count/$c)) . "%)\n";
	}
	else
	{
print "lame $c - $count/$c !>= 0.03, $c/$ivs !>= 0.03\n";
		last;
	}
}

my $newkey;
for (my $i = 0; $i < @key; $i++)
{
	if ($key[$i] == $i + 3)
	{
		chop($newkey);
		print "\nKey: $newkey (unlikely " . join(":", map { unpack("H2", chr($_)) } @key) . ")\n";
		$newkey = undef;
		last;
	}
	else
	{
		$newkey .= unpack("H2", chr($key[$i])) . ":";
	}
}

if ($newkey)
{
	print "\nKey: " . join(":", map { unpack("H2", chr($_)) } @key) . "\n";
}