Hex String XOR

[alanonymous]

Hello Monks!

I'm taking the free Stanford cryptography course, and while I have a decent basic understanding of perl, I'm having trouble doing the bit by bit and byte by byte XOR operations required. I've done a lot of googling, and I think I find solutions to what I am trying to do, but I don't understand how any of it actually works.

My questions:

1. How do you XOR two hex strings together? For instance, I give an input of say "aabbcc" and I want to XOR with "112233". The answer should be "bb99ff", but using $a ^ $b interprets as ascii instead of as hex values and so returns "PPPPPP". I suppose I just need to convert the string to a hex value, then the ^ would work? I'm not sure how.

2. This may be inherently related to question 1, but how do you convert between the 1 byte of hex and the ASCII representation of a character, and vice versa?

Thanks so much!

Alan

***********************************************************
Update 1

I think I am close with this ($t1 is string of hex characters, pushing ASCII to tk text box):

    my @ar = $t1 =~ /(..)/g;
    $foo->delete("1.0","end");
    foreach (@ar) {
        $foo->insert("1.0",chr(pack("H*",$_)));

    }

This *should* break the string into couplets, then for each couplet, turn it into the hex value of it's string hex self, then convert that hex value into ASCII with chr. It doesn't seem to work though :/



***********************************************************
Update 2

I got it to xor the two strings and output the hex result:

$txt3->delete("1.0","end");
    my $hexor = unpack('h*',pack('h*',$t1) ^ pack('h*',$t2));
    $txt3->insert("1.0",$hexor);

I'm still having trouble taking the hex string and finding the ascii character for it. Just testing:

my $hhh = unpack('h*',pack('h*',"20") ^ pack('h*',"61")); #xor ' ' and
+ 'a' should result in 'A'
    print unpack('h*',$hhh);

***********************************************************
***********************************************************
Solved!

Here's my code. Just takes 2 input strings of hex values, XORs them, then if that hex XOR is a real ASCII text character, returns the value, else just puts something obvious like ~.

sub parse () {

    my $t1 = $txt1->Contents();
    my $t2 = $txt2->Contents();
    chomp($t1);
    chomp($t2);

    $txt3->delete("1.0","end");
    my $hexor = unpack('h*',pack('h*',$t1) ^ pack('h*',$t2));
    $txt3->insert("1.0",$hexor);
    
    my @ar = $hexor =~ /(..)/g;
    $txt33->delete("1.0","end");
    foreach (@ar) {
        if (chr(hex($_)) =~ /[a-zA-Z]/) {
            $txt33->insert("end",chr(hex($_)));
        } else {
            $txt33->insert("end","~");
        }
    }
}

Thank you everyone for the help! And Marshall, I think you helped me last time I had a random question too!

[moritz]

You need to pack the hex representation into a binary string, so if you have '112233' you need to create the bytes "\x11\x22\x33". Then you can use the bitwise operators on these byte strings to do what you want.

Here's a nice way to do the conversions:

use strict;
use warnings;
use 5.010;  # just needed for say()

sub unascii {   pack 'h*', $_[0]; }
sub   ascii { unpack 'h*', $_[0]; }


say ascii unascii('aabbcc') ^ unascii('112233');
# output: bb99ff

See pack, unpack and perlpacktut for more details.

[ikegami]

"unascii" and "ascii" aren't very clear to me. I would call them "hex_to_bytes" and "bytes_to_hex" respectively.

[Marshall]

I know question #2, chr() and ord()

#!/usr/bin/perl -w
use strict;

printf "%X\n", ord('a');  #61
printf "%X\n", ord('b');  #62
print chr(0x61);          #a

still working on the best formulation for question #1. An issue is how to make it efficient.

Update: I think Moritz is on it.

pack() and unpack() are cool critters, but sometimes you have to stare at it for awhile. Example from the doc's:
sub ordinal { unpack("W",$_[0]); } # same as ord()

ord() and chr() are pretty "lightweight" critters. Without testing, I don't know if some kind of substr() based approach would be slower or faster. I assume for crypto, speed would be a major factor. On this performance point, I just don't know at the moment.

[Not_a_Number]

$a = 0xaabbcc;
$b = 0x112233;
printf '%X', $a ^ $b;

[Marshall]

I think this is good as far as it goes, but I would assume that the OP wants to XOR some humongous things that cannot be represented as simple Perl numeric scalar values? In this case, use hex() function.

my $x = "aabbcc"; 
my $y = "112233";

printf '%x', hex($x) ^ hex($y); #bb99ff

This causes integer overflow if $x and $y are "too big".

[rovf]

I give an input of say "aabbcc" and I want to XOR with "112233". The answer should be "bb99ff"

my $s='112233'; 
my $t='aabbcc'; 
my $x=hex($s)^hex($t); 
printf('%0x', $x);

[moritz]

Note that this solution too is limited by the size of the biggest integer you can store in a perl scalar, which is usally 52 bit from the mantissa of a double precision floating point, or 64 bit for an integer on 64bit platforms (not sure about the sign, so could be 63 usable bits for this purpose).

[tobyink]

Here's a solution that works on hex strings, so allows you to work with hex numbers larger than the maximum integers Perl can handle...

use 5.010;
use strict;
use Carp qw/croak/;
use List::Util qw/max/;

sub xor_strings
{
    croak "should be passed two arguments" unless @_==2;
    state $chunk_size = 4;
    state $pattern    = sprintf '%%0%dx', $chunk_size;
    
    # Make strings equal length, and a multiple of $chunk_size.
    my $length = max(map { length $_ } @_);
    $length += $chunk_size - ($length % $chunk_size);
    my @strings = map { ('0'x($length - length $_)) . $_ } @_;
    
    # Join results of each chunk
    return join q{},
        map {
            # Parse chunk hex to an integer
            my $i = $_;
            my @nums = map { hex substr $_, $i*$chunk_size, $chunk_siz
+e } @strings;
            # Xor them and convert to hex.
            sprintf $pattern, $nums[0] ^ $nums[1]
        }
        0 .. ($length/$chunk_size)-1;
}

say xor_strings(
    '112233112233112233112233112233112233112233112233112233',
    'aabbccaabbccaabbccaabbccaabbccaabbccaabbccaabbcc112233',
    );

The chunk size of 4 is fairly conservative. It means that the string in processed in four-digit (i.e. 16 bit) chunks. You can probably get a minor speed up using a larger chunk size if you know that your computer will be able to handle it. The returned value will be left-padded with zeroes to be a length that is a multiple of the chunk size.

[ikegami]

"^" converts floats to machine integers, so you're limited to 32/64, not 5253/64.

[Marshall]

Glad you have something working to your satisfaction!

Maybe not relevant here, but for future reference, there is a POSIX character class [:print:] that can be used in a Perl regex to emulate the C isprint() function. Throwing "non-printable" control characters to a terminal interface can cause "troubles" to say the least. Basically this character class says whether or not the "printer" can render this ASCII character on the screen.

[JavaFan]

Or, one could embrace the 21st century and use /\p{Print}/ instead of /[:print:]/. No need to restrict yourself to 256 code points, and subject yourself to locale. The era of 5.005 is over! ;-)

[Marshall]

Your point is well taken, however from the problem statement in this case, it appears that "bytes" are the unit of interest.