Cryptography Challenge – Collision (Medium): National Cyber League (NCL) 2015 Postseason

Oh, so you want a program “that find strings that have ‘nice’ digests.”

Fun fact, I had to go through 9,540,244,837 hashes to find the sha256! Editing the perl script [1] allowed for solving md5, sha1 and sha256. See the write up below regarding the question, answer, and solution code. For other National Cyber League content see Categories: NCL – Enjoy

Question 1:
What is an input that will yield an md5 hash that starts with D391B?

Answer 1:
“@^

echo -n '"@^' | md5sum | awk '{print toupper($0)}'
D3917551061C099469F49F4F4F1D4324  -

Solution 1:

#!/usr/bin/env perl

package Words;

sub new {
    my $class = shift;
    my $self = bless {}, $class;
    $self->{ 'next' } = [ 32 ];
    return $self;
}

sub next {
    my $self = shift;
    $self->increment();
    return pack( 'C*', @{ $self->{ 'next' } } );
}

sub increment {
    my $self = shift;
    my $N    = $self->{ 'next' };
    $N->[ -1 ]++;

    for ( my $i = $#{ $N } ; $i ; $i-- ) {
        return if $N->[ $i ] < 127;
        $N->[ $i ] = 33;
        $N->[ $i - 1 ]++;
    }

    if ( $N->[ 0 ] == 127 ) {
        $N->[ 0 ] = 33;
        unshift @{ $N }, 33;
    }
}

package main;

use Digest::MD5 qw( md5_hex );
use Time::HiRes qw( time );

$SIG{ INT } = sub { exit };

my $generator = Words->new();

#my $vanity   = '314159265358979323';
my $vanity = 'd391b';
my $search   = 4;
my $look_for = substr( $vanity, 0, $search );

my $print_speed = 1000000;
my $start_time  = time();

my $i = 0;
my $j = 0;
while ( 1 ) {
    my $word   = $generator->next();
    my $digest = md5_hex( $word );
    $i++;
    $j++;
    if ( $j == $print_speed ) {
        my $new_time = time();
        printf "%d hashes in %.3fs\n", $print_speed, $new_time - $start_time;
        $start_time = $new_time;
        $j          = 0;
    }
    next unless $look_for eq substr( $digest, 0, $search );
    printf "%10d : %-20s : %-10s : %s\n", $i, $word, $look_for, $digest;
    $search += 1;
    last if $search == length( $vanity );
    $look_for = substr( $vanity, 0, $search );
}

FILE: find.vanity.NCL-2015-Postseason.tar.gz

Question 2:
What is an input that will yield an sha1 hash that starts with 45EECA8?

Answer 2:
!Zxu’

echo -n '!'"Zxu'" | sha1sum | awk '{print toupper($0)}'
45EECA8E9BFCA37E76B30B8E873DC4527062508B  -

Solution 2:

#!/usr/bin/env perl

package Words;

sub new {
    my $class = shift;
    my $self = bless {}, $class;
    $self->{ 'next' } = [ 32 ];
    return $self;
}

sub next {
    my $self = shift;
    $self->increment();
    return pack( 'C*', @{ $self->{ 'next' } } );
}

sub increment {
    my $self = shift;
    my $N    = $self->{ 'next' };
    $N->[ -1 ]++;

    for ( my $i = $#{ $N } ; $i ; $i-- ) {
        return if $N->[ $i ] < 127;
        $N->[ $i ] = 33;
        $N->[ $i - 1 ]++;
    }

    if ( $N->[ 0 ] == 127 ) {
        $N->[ 0 ] = 33;
        unshift @{ $N }, 33;
    }
}

package main;

use Digest::SHA qw( sha1_hex );
use Time::HiRes qw( time );

$SIG{ INT } = sub { exit };

my $generator = Words->new();

#my $vanity   = '314159265358979323';
my $vanity = '45eeca8';
my $search   = 7;
my $look_for = substr( $vanity, 0, $search );

my $print_speed = 1000000;
my $start_time  = time();

my $i = 0;
my $j = 0;
while ( 1 ) {
    my $word   = $generator->next();
    my $digest = sha1_hex( $word );
    $i++;
    $j++;
    if ( $j == $print_speed ) {
        my $new_time = time();
        printf "%d hashes in %.3fs\n", $print_speed, $new_time - $start_time;
        $start_time = $new_time;
        $j          = 0;
    }
    next unless $look_for eq substr( $digest, 0, $search );
    printf "%10d : %-20s : %-10s : %s\n", $i, $word, $look_for, $digest;
    $search += 1;
    last if $search == length( $vanity );
    $look_for = substr( $vanity, 0, $search );
}

FILE: find.vanity.NCL-2015-Postseason.tar.gz

Question 3:
What is an input that will yield an sha256 hash that starts with 542715A3?

Answer 3:
!<21hA

echo -n '!<21hA' | sha256sum | awk '{print toupper($0)}'
542715A3959F733B0C9B63DEAE2C98B08F522720118D20D541FA1B6C81C2B118  -

Solution 3:

#!/usr/bin/env perl

package Words;

sub new {
    my $class = shift;
    my $self = bless {}, $class;
    $self->{ 'next' } = [ 32 ];
    return $self;
}

sub next {
    my $self = shift;
    $self->increment();
    return pack( 'C*', @{ $self->{ 'next' } } );
}

sub increment {
    my $self = shift;
    my $N    = $self->{ 'next' };
    $N->[ -1 ]++;

    for ( my $i = $#{ $N } ; $i ; $i-- ) {
        return if $N->[ $i ] < 127;
        $N->[ $i ] = 33;
        $N->[ $i - 1 ]++;
    }

    if ( $N->[ 0 ] == 127 ) {
        $N->[ 0 ] = 33;
        unshift @{ $N }, 33;
    }
}

package main;

use Digest::SHA qw( sha256_hex );
use Time::HiRes qw( time );

$SIG{ INT } = sub { exit };

my $generator = Words->new();

#my $vanity   = '314159265358979323';
my $vanity = '542715a3';
my $search   = 8;
my $look_for = substr( $vanity, 0, $search );

my $print_speed = 1000000;
my $start_time  = time();

my $i = 0;
my $j = 0;
while ( 1 ) {
    my $word   = $generator->next();
    my $digest = sha256_hex( $word );
    $i++;
    $j++;
    if ( $j == $print_speed ) {
        my $new_time = time();
        printf "%d hashes in %.3fs\n", $print_speed, $new_time - $start_time;
        $start_time = $new_time;
        $j          = 0;
    }
    next unless $look_for eq substr( $digest, 0, $search );
    printf "%10d : %-20s : %-10s : %s\n", $i, $word, $look_for, $digest;
    $search += 1;
    last if $search == length( $vanity );
    $look_for = substr( $vanity, 0, $search );
}

FILE: find.vanity.NCL-2015-Postseason.tar.gz
Reference:

[1] https://github.com/depesz/vanity-hash-finder/blob/master/find.vanity.md5.by.rhodiumtoad.pl