XOR Binary Stream Against a Known Binary Key

telecom_is_me · 07-02-2008, 10:39 PM

I'm trying to xor a known binary key against a stream of incoming binary. The key is a fixed length that repeats over and over again because the stream is continuous.

I've come up with this is perl:

Code:

#!/usr/bin/perl

$/ = '';                                                                                                # The Read In From Memory

while (<>) {                                                                                            # The While Loop Starts
  chomp;                                                                                                # Read The Input In with stdin
        $key = "1111111111111111111011000101000001010000010100000000001000000100000001100000000";       # Cypher Key
        $crypt = $_ ^ $key;                                                                             # Run The XOR
        print "$crypt\n";                                                                               # Print The Output
}                                                                                                       # The While Loop Ends

But it doesn't seem to actually work, the output looks very strange, it's definitely not XOR'd.

Here's my sample input:

Code:

$ cat bin.txt
11110110111101101111011000101000001010000010100000000001000000100000001100000000
10011100001111000000010001011111001100000101100111101101111010101110000110001100
10001100000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000010101010000010001011111001100000101100111101101
00110011111111110011011100000000000000000000000000000000000000000000000000000000
11010001100111000011110000000100010111110011000001011001111011011110101011100001
00000000000000000000000000000000000000000000000000000000000000000000000000000000
10110011011100011010101011010001100111000011110000000100010111110011000001011001
00000000000000000000000000000000000000000000000000000000000000000000000000000000

Here's my sample output:

Code:

$cat bin.txt | perl xor.pl
0
10011100001111000000010001011111001100000101100111101101111010101110000110001100
10001100000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000010101010000010001011111001100000101100111101101
00110011111111110011011100000000000000000000000000000000000000000000000000000000
11010001100111000011110000000100010111110011000001011001111011011110101011100001
00000000000000000000000000000000000000000000000000000000000000000000000000000000
10110011011100011010101011010001100111000011110000000100010111110011000001011001
00000000000000000000000000000000000000000000000000000000000000000000000000000000

Very Strange: I don't know where that leading 0 comes from, as well as the fact that the XOR isn't working properly.

Mr. C. · 07-03-2008, 12:21 AM

You are XORing two strings.

Code:

$ perl -e 'print 2 ^ 1, "\n"'
3
$  perl -e 'print "2" ^ "1", "\n"'

$

telecom_is_me · 07-03-2008, 07:59 AM

Quote:

Originally Posted by Mr. C.

You are XORing two strings.

Code:

$ perl -e 'print 2 ^ 1, "\n"'
3
$  perl -e 'print "2" ^ "1", "\n"'

$

I realized that when I looked at it fresh this morning, that's why there's a leading 0 in the result...

However I've tried the statement above and I'm not getting the results I would hope for:

Code:

perl -e 'print 0110 ^ 1001, "\n"'

I would expect a result of 1111, not 929. Could it be that it's treating the result as decimal and not binary?

ntubski · 07-03-2008, 10:51 AM

Code:

~/tmp$ perl -e 'printf ("%04b\n" ,(0b0110 ^ 0b1001))'
1111

First the input is treated as decimal if it's not prefixed with 0b, ie 1001 is one thousand and one, not 9. Second, print will show numbers in decimal.

telecom_is_me · 07-03-2008, 02:22 PM

Quote:

Originally Posted by ntubski

Code:

~/tmp$ perl -e 'printf ("%04b\n" ,(0b0110 ^ 0b1001))'
1111

First the input is treated as decimal if it's not prefixed with 0b, ie 1001 is one thousand and one, not 9. Second, print will show numbers in decimal.

Ok looks good however when I create a script out of it and try to read input as follows:

Code:

#!/usr/bin/perl

$/ = '';                                                                                              # The Read In From Memory

while (<>) {                                                                                          # The While Loop Starts
  chomp;                                                                                              # Read The Input In with stdin
        $key = 0b1111111111111111111011000101000001010000010100000000001000000100000001100000000;     # Cypher Key
        printf ("%04b\n", ($_ ^ $key));                                                               # Print The Output
}

I get some strange results like:

Code:

echo 1111111111111111111011000101000001010000010100000000001000000100000001100000000 | perl scripts/descrambler.pl
Integer overflow in binary number at scripts/descrambler.pl line 7.
0000

Again I suspect that the problem is that the script is reading in the binary as decimal, however when I use 0b$_ it fails.

Mr. C. · 07-03-2008, 03:25 PM

By my count, that's a 79-bit number.

perldoc Math::BigInt

telecom_is_me · 07-03-2008, 04:01 PM

Ok so I added biginit with a use statement "use Math::BigInt;" however the function still errors out with an error of "Integer overflow in binary number at scripts/descrambler.pl"

Mr. C. · 07-03-2008, 04:52 PM

DESCRIPTION
All operators (inlcuding [sic] basic math operations) are overloaded if you
declare your big integers as

$i = new Math::BigInt '123_456_789_123_456_789';

Operations with overloaded operators preserve the arguments which is
exactly what you expect.

sundialsvcs · 07-03-2008, 07:33 PM

I don't think that "BigInt" is the right way to solve this problem. That tool is really intended for unlimited-precision mathematics. Not the right Swiss Army knife for this job, methinks.

I'm not actually quite sure what is the best tool for XORing a buffer in Perl. Maybe a group like [url]http://www.perlmonks.org[/i] could point you in the right direction and you could summarize it here.

telecom_is_me · 07-03-2008, 07:50 PM

Quote:

Originally Posted by Mr. C.

DESCRIPTION
All operators (inlcuding [sic] basic math operations) are overloaded if you
declare your big integers as

$i = new Math::BigInt '123_456_789_123_456_789';

Operations with overloaded operators preserve the arguments which is
exactly what you expect.

I get it, so you have to declare it with a "use" statement first then include it in the function it's self... "http://perl.active-venture.com/lib/Math/BigInt.html" seemed useful and I managed to come up with the following:

Code:

#!/usr/bin/perl

$/ = '';                                                                                              # The Read In From Memory
use Math::BigInt;

while (<>) {                                                                                          # The While Loop Starts
  chomp;                                                                                              # Read The Input In with stdin
        my $input = new Math::BigInt $_;
        my $key = new Math::BigInt '0b1001111111111111111011000101000001010000010100000000001000000100000001100000000';     # Cypher Key
        my $cyphertext = new Math::BigInt ($input ^ $key);
        printf (int ($cyphertext), "\n");                                                               # Print The Output
           }

However it still doesn't return an all binary stream as a result of the xor. As you can see from the following:

Code:

$ echo 1111111111111111111011000101000001010000010100000000001000000100000001100000000 | perl xor.pl
1111111111111111111011000101000001010000010100000000001331120171658243462440960

Any ideas why it still isn't treating it correctly?

telecom_is_me · 07-03-2008, 07:59 PM

I had another go at this and I'm still getting funky results, in one iteration I got a NaN error which apparently means not a number, so I took the quotes off of both the input and key which means they are no longer character strings but instead pure numbers, however it still doesn't work:

Code:

#!/usr/bin/perl

$/ = '';                                                                                              # The Read In From Memory
use Math::BigInt;

while (<>) {                                                                                          # The While Loop Starts
  chomp;                                                                                              # Read The Input In with stdin
        my $input = new Math::BigInt ($_);
        my $key = new Math::BigInt (0b1001111111111111111011000101000001010000010100000000001000000100000001100000000);     # Cypher Key
        my $cyphertext = new Math::BigInt ((int($input)) ^ (int($key)));
        printf (int ($cyphertext), "\n");                                                               # Print The Output
           }

I get the following when I try it:

Code:

echo 1111111111111111111011000101000001010000010100000000001000000100000001100000000 | perl xor.pl
Integer overflow in binary number at xor.pl line 9.
1111111111111111111011000101000001010000010100000000001331120171658243875683584

I'm not sure why I'm still getting the integer overflow error on line 9.

telecom_is_me · 07-03-2008, 08:14 PM

OK, so one of the problems I've determined is still that the input is not being represented as binary. By manually a-fixing 0b to the input from the echo that it gets rid of one problem but I can't seem to get it to read in that way automatically.

Mr. C. · 07-03-2008, 11:20 PM

Right, "use" or "require" import the library and its namespace into your program. You must actually invoke the methods or functions, in this case, to overload the data types such that the arithmetic operators "just work" as you'd expect. But until you've called "new" in this case, your data types are standard perl data types.

I was wondering why you don't split the data into 32-bit chunks, and perform your XOR on the 32-bit integers. Why try to perform large integer arithmetic, when instead you can let the math processor work for you. Split your 79 character binary string into 32, 32 and 15-bit binary representations, XOR each of those chunks, and output as you see fit.

telecom_is_me · 07-04-2008, 05:41 PM

Well, it sounds like a good idea, however the sequence will repeat as more and more data flows in, for instance if I have a binary stream that lets say for the sake of argument 1000 bits long, my key which is 79 bits long will repeat over and over again until it's been XOR'd against the entire stream.

Perhaps i should look at this another way, My plan was to create by hand the full 1000bit key based on a stream length of 1000 / a 79 bit key ~= 13 repetitions of the key - and extra 27 bits... and then use that full key to XOR against the full stream.

Maybe I should go about this by creating 79 individual variables and assigning them each 1 bit of the key, then by doing so I would be able to have a loop run a xor of the first variable against the first incoming bit in the stream and so on for 79 times then have the loop reset to variable 1 "key bit one".

Does that seem like a feasible solution?

Mr. C. · 07-04-2008, 07:10 PM

You could do that, pre-creating an array of key length size, and creating a shift register, xor'ing one bit at a time. Here's an example;

Code:

#!/usr/bin/perl

@key = qw ( 2 4 6 1 0 1 2 0 7 );
@str = qw ( 4 9 0 3 2 9 8 1 3 4 5 2 6 8 );

print "Str: @str\n";
print "Key: @key\n";
while (defined ($strbit = shift @str)) {
   $keybit = shift @key;
   push @key, $keybit;
   print "strbit: $strbit, keybit: $keybit\n";
}

This can be made slightly more efficient, but I've expanded it so that you can see what happens. I've also used single digits in the key and bit stream so it is easier to see how it works. Change them to binary 0 or 1, and instead of printing out, perform your XOR.

This certainly is very inefficient for large data sets. It would be better to work in architecture-sized ints, so that the hardware could do a single XOR on all 32 bits. You could pre-compute N full length key segments, and the various permutations of the cycled remainder key bits.