Subject: [IPsec] Comments to draft-song-ipsecme-seq-icv-01

From: Tero Kivinen <[email-masked]>
Date: Wed, 9 Oct 2013 17:36:14 +0300

The new SEQ-ICV calculation is no more safer than the previous one. It
is trivial to break it:

       SEQ-ICV = (SEQ + ICV[0-3]) ^ K[0-3] +
               (SEQ + ICV[4-7]) ^ K[4-7] +
               (SEQ + ICV[8-11]) ^ K[8-11]

The problem is that lowest byte of the SEQ-ICV only depends on the
K[3] + K[7] + K[11], as the SEQ and ICV is known to the attacker. So
attacker needs to do O(2^24) work to crack the 3 bytes from the key.
For the next 3 bytes it needs to do same, and so on. So the total
complexity of the SEQ-ICV is O(4*2^24) = O(2^26), i.e. around 67
million tries. In my attacked perl script the cracking can be done
after seeing around 50 packets with valid SEQ, ICV, SEQ-ICV triplets,
and the main reason it requires 50 packets is that I try 10 packets
before I am convinced that my guess for the 3 bytes is correct before
moving to the next byte, so 4 * 10 == 40 would be the mimimum... The
run time of my attack script is less than 20 seconds... And time to
implement that script was around an hour, inventing the method to
start attacking against it took less than the time to run the final
script.

I think it is pointless to try to invent new semi-cryptographic
protection for the sequence numbers as it most likely will be
trivially broken when someone starts to really look at in. I am no
cryptographer, and even I could break last two tries, and even if you
manage make method I cannot break, I am sure real cryptographers can
break it in no time.

If we want to use cryptographic strong hash/mac, we need to use real
cryptographic strong hashes / macs, not try to invent something
ourselves. And we already have cryptographic strong ICV there, so lets
use that instead.

(Yes, I know the script is not very pretty and it is a hack, and it
uses rand() to generate random numbers, but as for this testing I just
needed some random packets, so no cryptographically strong randomess
was actually needed).

#!/usr/pkg/bin/perl -w
# -*- perl -*-
######################################################################
# song-crack.pl -- Crack to draft-song-ipsecme-seq-icv 
# Copyright (c) 2013 Tero Kivinen
# All Rights Reserved.
######################################################################
#         Program: song-crack.pl
#	  $Source:  $
#	  Author : $Author: kivinen $
#
#	  (C) Tero Kivinen 2013 <[email-masked]>
#
#	  Creation          : 16:04 Oct  9 2013 kivinen
#	  Last Modification : 17:34 Oct  9 2013 kivinen
#	  Last check in     : $Date:  $
#	  Revision number   : $Revision:  $
#	  State             : $State: Exp $
#	  Version	    : 1.35
#	  Edit time	    : 74 min
#
#	  Description       : Crack draft-song-ipsecme-seq-icv-01
#
#	  $Log:  $
#
#
#
######################################################################
# initialization

require 5.002;

# Secret key we are trying to guess, this is only used to
# calculate proper values for the SEQ-ICV
$k = "RandomKey123";
($k1, $k2, $k3) = unpack("NNN", $k);

# Initial sequence number for packets, after this we just use
# next sequence number.
$seq = int(rand(0x10000)) * 0x10000 + int(rand(0x10000));

# How many packets and how long it takes to run this script.
$packets = 0;
$start = time();

# Internal state of the cracking, i.e. this is the key
# we are trying now. 
$Crack::k1 = 0; 
$Crack::k2 = 0; 
$Crack::k3 = 0;

# Packets we have already seen, every time we find new guess
# for the key, we go through all of these and verify
# the key works for them too. 
@Crack::seqs = ();
@Crack::icv1 = ();
@Crack::icv2 = ();
@Crack::icv3 = ();
@Crack::seq_icv = ();

# Which byte we are trying to crack, and how many proper
# packets we have already found for that. 
$Crack::byte = 0;
$Crack::found = 0;

# Limit how many packets we check before we assume this key is ok.
# Note, that this code does not go back incrementing the earlier bytes
# if we do not find key, so setting this too low will cause the
# script not to find key. Setting this lower will require less packets.
$Crack::limit = 10;

# Loop until we have cracked the whole key. 
while ($Crack::byte < 4) {
    # Generate packet, i.e. genereate random ICV and calculate SEQ-ICV
    printf("Packet %d, finding byte %d\n", $seq, $Crack::byte);
    $icv = pack("n6", int(rand(0x10000)), int(rand(0x10000)),
		int(rand(0x10000)), int(rand(0x10000)),
		int(rand(0x10000)), int(rand(0x10000)));
    ($icv1, $icv2, $icv3) = unpack("NNN", $icv);
    $seq_icv = (((($seq + $icv1) & 0xffffffff) ^ $k1) +
		((($seq + $icv2) & 0xffffffff) ^ $k2) +
		((($seq + $icv3) & 0xffffffff) ^ $k3)) & 0xffffffff;
    printf("ICV = %s, seq_icv = %08x\n", unpack("H*", $icv), $seq_icv);

    # Give that SEQ, ICV, and SEQ-ICV to the cracking engine
    try_crack($seq, $icv1, $icv2, $icv3, $seq_icv);

    # Move to next packet
    $seq++;
    $packets++
}

# Print out the results
printf("Found key in %d packets, %d seconds\n", $packets, time() - $start);
printf("Key = %s\n", pack("NNN", $Crack::k1, $Crack::k2, $Crack::k3));
exit(0);

######################################################################
# Try to find key that matches the SEQ, ICV, SEQ-ICV triplet given
# in. 

sub try_crack {
    my($seq, $icv1, $icv2, $icv3, $seq_icv) = @_;
    my($seq_icv_val, $seq_icv_try, $mask, $inc, $mask2);

    # Check which byte we are cracking
    if ($Crack::byte == 0) {
	$mask = 0xff;
	$mask2 = 0xff;
	$inc = 1; 
    } elsif ($Crack::byte == 1) {
	$mask = 0xffff;
	$mask2 = 0xff00;
	$inc = 0x100;
    } elsif ($Crack::byte == 2) {
	$mask = 0xffffff;
	$mask2 = 0xff0000;
	$inc = 0x10000; 
    } elsif ($Crack::byte == 3) {
	$mask = 0xffffffff;
	$mask2 = 0xff000000;
	$inc = 0x1000000; 
    }
    $seq_icv_val = $seq_icv & $mask;

    # Loop for possible keys until we find a hit. 
    while (1) {
	# Calculate SEQ-ICV for our guessed key. 
	$seq_icv_try = (((($seq + $icv1) & $mask) ^ ($Crack::k1 & $mask)) +
			((($seq + $icv2) & $mask) ^ ($Crack::k2 & $mask)) +
			((($seq + $icv3) & $mask) ^ ($Crack::k3 & $mask))) &
			$mask;
	# Check if it was a match.
	if ($seq_icv_val == $seq_icv_try) {
	    # It was, check for the earlier packets. 
	    if (check_rest($mask)) {
		# They matched too, add the packet to the pool
		add_packet($seq, $icv1, $icv2, $icv3, $seq_icv);
		# Did we find enough packets that match our current key
		# if so move to next byte
		if ($Crack::found > $Crack::limit) {

		    # Print out the current key before moving to next byte
		    if ($Crack::byte == 0) {
			printf("Key = ***%c***%c***%c\n",
			       $Crack::k1 & 0xff, 
			       $Crack::k2 & 0xff, 
			       $Crack::k3 & 0xff);
		    } elsif ($Crack::byte == 1) {
			printf("Key = **%c%c**%c%c**%c%c\n",
			       ($Crack::k1 >> 8) & 0xff,
			       $Crack::k1 & 0xff,
			       ($Crack::k2 >> 8) & 0xff,
			       $Crack::k2 & 0xff, 
			       ($Crack::k3 >> 8) & 0xff,
			       $Crack::k3 & 0xff);
		    } elsif ($Crack::byte == 2) {
			printf("Key = *%c%c%c*%c%c%c*%c%c%c\n",
			       ($Crack::k1 >> 16) & 0xff,
			       ($Crack::k1 >> 8) & 0xff,
			       $Crack::k1 & 0xff,
			       ($Crack::k2 >> 16) & 0xff,
			       ($Crack::k2 >> 8) & 0xff,
			       $Crack::k2 & 0xff, 
			       ($Crack::k3 >> 16) & 0xff,
			       ($Crack::k3 >> 8) & 0xff,
			       $Crack::k3 & 0xff);
		    } elsif ($Crack::byte == 3) {
			printf("Key = %c%c%c*%c%c%c*%c%c%c*\n",
			       ($Crack::k1 >> 24) & 0xff,
			       ($Crack::k1 >> 16) & 0xff,
			       ($Crack::k1 >> 8) & 0xff,
			       $Crack::k1 & 0xff,
			       ($Crack::k2 >> 24) & 0xff,
			       ($Crack::k2 >> 16) & 0xff,
			       ($Crack::k2 >> 8) & 0xff,
			       $Crack::k2 & 0xff, 
			       ($Crack::k3 >> 24) & 0xff,
			       ($Crack::k3 >> 16) & 0xff,
			       ($Crack::k3 >> 8) & 0xff,
			       $Crack::k3 & 0xff);
		    }
		    $Crack::byte++;
		    $Crack::found = 0;
		}
		# Found candidate key, move to next packet
		return;
	    }
	}
	# This key was no match, increment key, and try again
	$Crack::k1 = ($Crack::k1 + $inc) & $mask;
	if (($Crack::k1 & $mask2) == 0) {
	    $Crack::k2 = ($Crack::k2 + $inc) & $mask;
	    if (($Crack::k2 & $mask2) == 0) {
		$Crack::k3 = ($Crack::k3 + $inc) & $mask;
		if (($Crack::k3 & $mask2) == 0) {
		    die "Could not find key";
		}
	    }
	}
    }
}

######################################################################
# Check that the earlier received packets match too.

sub check_rest {
    my($mask) = @_;
    my($i, $seq_try);

    # Loop through all packets received before and check them
    for($i = 0; $i <= $#Crack::seqs; $i++) {
	$seq_try = (((($Crack::seqs[$i] + $Crack::icv1[$i]) & $mask)
		     ^ ($Crack::k1 & $mask)) +
		    ((($Crack::seqs[$i] + $Crack::icv2[$i]) & $mask)
		     ^ ($Crack::k2 & $mask)) +
		    ((($Crack::seqs[$i] + $Crack::icv3[$i]) & $mask)
		     ^ ($Crack::k3 & $mask))
		    & $mask);
	# Check if it is match, if not return error, which
	# causes the try_crack to move to next key
	if (($Crack::seq_icv[$i] & $mask) != $seq_try) {
	    $Crack::found = 0;
	    return 0;
	}
    }
    # All matched, so mark this as found
    $Crack::found++;
    return 1;
}

######################################################################
# Add packet to the pool to be checked.

sub add_packet {
    my($seq, $icv1, $icv2, $icv3, $seq_icv) = @_;

    push(@Crack::seqs, $seq);
    push(@Crack::icv1, $icv1);
    push(@Crack::icv2, $icv2);
    push(@Crack::icv3, $icv3);
    push(@Crack::seq_icv, $seq_icv);
}

######################################################################
# EOF
######################################################################
-- 
[email-masked]