Warning: closedir() expects parameter 1 to be resource, null given in /home/aware/public_html/etc/gamma/index.php on line 23
.aware gamma zine - The BF Challenge Analysis
.aware eZine Gamma - Kung Foo Training Kamp
γ
Ω


[==============================================================================]
[--------------------------[ The Brainfuck Challenge ]-------------------------]
[==============================================================================]


       _.d####b._
     .############.
   .################.
  .##################.__ __ __ __ _ _ __ __ 
  ##############/_`|#\ V  V // _` | '_/ -_)
  ##############\__,|# \_/\_/ \__,_|_| \___|
  ###########>"<######    
  *#########(   )####* 
   ##########>.<#####    author: zshzn
    ################      email: vzshzn|gmail|com
     *############*       
       "T######T"



--[ 00 ]----------------------------------------------[ Table Of Contents ]-----


  1 The Challenge
    1.1 Brainfuck
    1.2 Translating
    1.3 Understanding
  2 Wordlist Attack 
    2.1 filter.c
    2.2 Results
  3 Cryptanalysis
    3.1 Kasiski Method
    3.2 Z Method
    3.3 Analysis
    3.4 Alternative
  4 Known Plaintext Attack
    4.1 Motivation
    4.2 kpt.pl
    4.3 Results
  5 Conclusions



--[ 01 ]--------------------------------------------------[ The Challenge ]-----


In the last zine rattle published a small challenge, a simple brainfuck
programs with no instructions. This little piece explains how I went
about attacking the challenge.

1.1 Brainfuck

                      __gd++++++++++[>+++>++bp__
                   _g++++>+P^^""j+++"^""^^++++<<<p_
                _g-]>>^>.+b    d++ +;       ""^^+++.p_
              _d[-]^"  :<-    -.[                "^-]<b_
            _d++.'      [-b_   ]>b                  `---b_
           d---'      _gg----bpd[++p_d+bpp_           `+++b
          d+++      _d+>,----------]<[[>]<bp_           [>>b
         d+<<      d[<]<++>>[>]<-]<[[>>+<<[<]b_          <->b
        d>[>      d]<-]<[<]]>]<++++++P^^T+++++            +++b
       d++[    '<-------->-]<[[-]++++bggpd++++b_           ++[b
      :>++      _+++++++<-]>---.-----.---.-.-----p___g_     --.;
      <<];     d>>>>[[[<<<<+>>>>-]>]<<<+^"^++++++^^+++[;    :>--
     :---     :>--->---->----:->-------_    "^--bpd>---_     ---;
     ---;     :-->---------->b------>^^--p_    `--->---;     :---
    :>--      :--->---->------ `^^^'    "^>-p_    l-`->       ---;
    :---      >---->---------              `-->p__;-b         ---;
    >--;      -->---->------;                `-----:>b        :---
    ---;      >---------->---                        -b    _  :---
    :---     d->--->---->----_                        -b___-b >--;
    :---  _g->---->------>-----p____________gp__      :-`^^^' >--;
     -->;  `^^'----------->--->----->---->-------p_    -b___ :->-
     :---       ->----->----->---->---------->-----b_   "^"  ---;
      -->;       `----------->------>----------->----b      :---
      :---        >----->------>---->----->---------->;     ---;
       ---b    _  :>-`--->----->----->----->------>----;   d---
        ---b   >----; :>---->----[<]>-]>--->-->+>+++>++>  d>++
         >++b   `^^'  +>+ "^++>++++>->----->>----->+++>- d---
          >>-b        --     ->--->----->++>->++++>>+>-;d->+
           +>+b_      '       +>->>+>++>->--->-->--->---->+
            `+++>p_          d>->----->++++>+>+>+++>+++>-'
              `-->--p______g--->++>+++>++++>++>+++>----'
                "^>+++>++++>>++++>>----->->----[<]>[^"
                   "^<<+<[<]>[[>]<+>>-<<[<]>-]>[>^"
                       ""]<->>.[-]>]]++++++++++."


1.2 Translating

To understand the code, first I translated it into a language that I could
debug more easily. I could use gdb (and a C brainfuck interpreter) or a
custom-built brainfuck debugger, but instead I took this avenue. I used some
bf-to-perl translator, and then I split it into understandable chunks, added
some commenting, and made a tiny eightbit implementation. Unfortunately I did
not optimize the actual output, so it's very dirty and repetitive.

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dumper;

use constant OVERLOAD => 1;

package Eightbit;

sub new 
{
    my ($class, $start) = @_; 
    bless { VAL => ($start || 0) % 256 }, $class;
}

# The reason I do the is because rattle (and bf programmers in general) abuse
# integer overflow. So what are negative numbers in Perl (or excessively large
# numbers) actually wrapped in eightbit (standard) bf implementations

# This is horribly dirty. 
# Very incomplete implementation of an eight-bit data type.
use overload
    '++'   => sub { ++$_[0]->{VAL}; $_[0]->{VAL} %= 256 },
    '--'   => sub { --$_[0]->{VAL}; $_[0]->{VAL} %= 256 },
    'bool' => sub { $_[0]->{VAL} };

package main;

# Ugh.
my @m;
my $p = 0;

# You may wonder just why I create an array of Eightbit objects, instead of one
# object that acts as a container for eight-bit items.
# Elementary, Watson. I already had the Perl generated, and did not want to
# change all my $m[$p] to $m->{$p} or $m->item($p) or any other interface!
OVERLOAD and $m[$_] = new Eightbit for 0 .. 80;

# My debugging subs, of course
# I don't think they are in use in the program as I've copied it, but they were
# crucial to understanding it.
sub display
{
    print "\nindex: $p\n";
    print "\@m[$_] = $m[$_]\n" for 0 .. $#m;
    # print "\@m[$_] = $m[$_]:@{[chr $m[$_]]}\n" for 0 .. $#m;
}

sub marker { print "\n[here]\n"; }

sub i { print "\nindex: $p\n"; }

# Commence program

# Printing "PW: "
$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;
$m[$p]++;$m[$p]++;

while($m[$p]){

;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;
$m[$p]++;$m[$p]++;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;
$m[$p]++;$m[$p]++;$p--;$p--;$p--;$m[$p]--;
};
$p++;$p++;$p++;
print chr $m[$p];
$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;
print chr $m[$p];

while($m[$p]){$m[$p]--;}

$p--;$m[$p]--;$m[$p]--;
print chr $m[$p];

while($m[$p]){$m[$p]--;};

$p--;$m[$p]++;$m[$p]++;
print chr $m[$p];

# INPUT
while($m[$p]){$m[$p]--;}

$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;

while($m[$p]){

$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;
$m[$p]++;$m[$p]++;$p++;
    $m[$p]= new Eightbit(ord getc);

$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;
};


$p--;

# Input of ABCDEF gets us:
# \0\0\0ABCDEF
# password starts at $m[3]

# Note that rattle tends to index from 1
# Basically leaving $m[0] = 0 lets him find the bottom easily
# He will do: [-]. To us: while ($m[$p]) { $p-- } to reduce the index value
# until hitting a blank value

# It takes a bit of effort to travel from one end of the array to the other
# So rattle has variables, then a blank entry, then the password, then a blank
# entry, then more variables. That's probably the best way to do it.
# So note that he uses counters that are positioned before and after strings

while($m[$p]) {
  while($m[$p]){;
    $p++; # Go to the back of the string (excluding counters at end)
  };
  $p--; # Down one, last item in password
  while($m[$p]){;
    $p++;$p++;$m[$p]++;$p--;$p--; # Increase point two chars right by 1 (some
                                  # extra counter val)
    while ($m[$p]) { $p--; } # Get down to before password
    $p--;  
    $m[$p]++;$m[$p]++; # Counter $m[1] += 2
    $p++;$p++; # Counter to start of pw
    while($m[$p]){;
      $p++;
    };
    $p--; # Last char
    $m[$p]--; # last char -1
    
  };
  # We have eliminated the last letter, on to the one before it
  $p--;
  while($m[$p]){;
    while($m[$p]){;
      $p++;$p++;$m[$p]++;$p--;$p--;
      while($m[$p]){;
      $p--;
      };
      $p--;
      $m[$p]--; # $m[1]--
      $p++;$p++;
      while($m[$p]){;       # Same deal, just increase counter by one
                            # instead of two 
    $p++;
      };
      $p--;
      $m[$p]--;
    };
    $p--;
    while($m[$p]){;
      $p--;
    };
  };
  
 $p++;
};

# We have added double the last letter in the password to Counter 1, then
# subtracted the second last from Counter 1
# We continue left:
# ABCDEF -> FEDCBA -> 70*2 - 69 + 68*2 - 67 + 66*2 - 65
# Rather oddly he has shifted the entire string two characters to the right

$p--;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;
$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;
# $m[2] = 16;
while($m[$p]){;
 
$p--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$p++;$m[$p]--;
};
# $m[1] -= 128


$p--;

OVERLOAD or $m[1] %= 256;
# Brainfuck values exist in eight-bit chars.
# You can do the above to make the hash work if you don't want to use 
# overloading


# $m[1] = 0; # Uncomment this to bypass the next part if you're too lazy to use
             # a real password
# I test with the passwords "        " and "0chunk"
# The first is perfectly balanced, the second abuses overflow.

# This loop just destroys our hard work to produce WRONG
while($m[$p]){;
  while($m[$p]){;
    $m[$p]--;
  };

$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;
$m[$p]++;$m[$p]++;
  # $m[1] = 10;

  while($m[$p]){;

$p++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;
$m[$p]++;$p--;$m[$p]--;
  }
  ;$p++;$m[$p]--;$m[$p]--;$m[$p]--;

  # BEGIN printing WRONG
  print chr $m[$p];
  $m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
  print chr $m[$p];
  $m[$p]--;$m[$p]--;$m[$p]--;
  print chr $m[$p];
  $m[$p]--;
  print chr $m[$p];
  $m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
  print chr $m[$p];
  # END printing WRONG
  $p--;$p--;

}
# To avoid losing, $m[1] must equal 0

# See how that worked? He "hashes" the password you give him
# If the sum of two times the even letters (by reverse index) sub the odd
# letters equals 128, you move on

# This still allows for a nearly unlimited (other than by interpreter) amount
# of possible working passwords, restricted to eightbit hash space.
# Basically 1/256 of possibilities will pass since we're in eight-bit space.
# I prefer "        ", it's fun!

# Now our PW is stored in indexes $m[5] and up

$p++;$p++;$p++;$p++;
# Get to the first char

# This condition fails if our hash failed, and the program falls through to
# termination
while($m[$p]){;
  while($m[$p]){;
    while($m[$p]){;
      $p--;$p--;$p--;$p--;$m[$p]++;$p++;$p++;$p++;$p++;$m[$p]--;
    }
    $p++;
  }
  # we move it to $m[1] and up


;$p--;$p--;$p--;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;
$m[$p]++;$m[$p]++;$m[$p]++;
  # to right of last char is 10

  while($m[$p]){

$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;
$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;

$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;
$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;;;$m[$p]--;$m[$p]--;$m[$p]--;$p++;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;;;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;;;$p++;$m[$p]--;$m[$p]--;;;$m[$p]--;$m[$p]--;$p++;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;;;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;;;$p++;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$p++;$m[$p]--;$m[$p]--;;;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;
$m[$p]--;$m[$p]--;;;$m[$p]--;$m[$p]--;$p++;;;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;
$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;;;$m[$p]--;$m[$p]--;$p++;;;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;;;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;;;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++
;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;;;$p++;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;

    while($m[$p]){;$p--;};
    $p++;$m[$p]--;
  };

$p++;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$p++;$m[$p]++;$p++;
$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]++;$m[$p]++;$p++;$p++;$m[$p]++;$m[$p]++;
$p++;$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]++;
$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$p++;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;
$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$p++;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$p++;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]++;$m[$p]++;$p++;
$m[$p]--;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$p++;$p++;$m[$p]++;$p++;
$m[$p]--;$m[$p]--;$p++;$m[$p]++;$m[$p]++;$p++;$m[$p]++;$m[$p]++;$p++;$m[$p]--;
$p++;$p++;$m[$p]++;$p++;$m[$p]++;$m[$p]++;$p++;$m[$p]--;$p++;$m[$p]--;$m[$p]--;
$m[$p]--;$p++;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$p++;$p++;
$m[$p]--;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]++;
$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]++;$p++;$m[$p]++;$p++;$m[$p]++;$m[$p]++;
$m[$p]++;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]--;$m[$p]--;$m[$p]--;$p++;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]++;$m[$p]++;$p++;
$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$p++;
$m[$p]++;$m[$p]++;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]--;$m[$p]--;
$m[$p]--;$m[$p]--;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$p++;$m[$p]++;$m[$p]++;
$m[$p]++;$m[$p]++;$p++;$p++;$m[$p]++;$m[$p]++;$m[$p]++;$m[$p]++;$p++;$p++;
$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$m[$p]--;$p++;$m[$p]--;$p++;$m[$p]--;
$m[$p]--;$m[$p]--;$m[$p]--;

while($m[$p]){;$p--;};
$p++;

# You may ask what that massive crap did.
# What it did was fill out a string of 62 characters
# This is the template of our phrase, the ciphertext


OVERLOAD or $m[$_] = $m[$_] % 256 for 0 .. $#m;
# Another normalization hack if you do not want to overload

# Our ciphertext is:
# 203 224 217 209 168 146 158 199 209 200 205 211 196 221 199 212 146 212 213
# 211 148 195 160 146 227 214 198 198 215 196 197 218 145 223 204 213 162 210 206
# 205 211 160 157 147 199 149 153 201 198 219 210 158 199 212 209 210 206 200 156
# 211 215 212

# display();
# exit;

# Start at first char of phrase
# Current structure is:
# 0 password 0 j ciphertext

while($m[$p]){;
  $p--;$p--;$m[$p]++; # counter++
  # display() if $d < 5;$d++;
  $p--;
  while($m[$p]){
    ;$p--;
  };
  $p++; # Down to bottom (1)
  while($m[$p]){
    while($m[$p]){;
      $p++;
    };
    $p--; # Counter right after password?
    $m[$p]++; # ++
    $p++;$p++;
    $m[$p]--; # -- first char of phrase
    $p--;$p--;
    while($m[$p]){
      $p--;
    };
    $p++;$m[$p]--;
    # Back down to 1, subtract one
  };
  $p++;
  while($m[$p]){
    ;$p++;
  };

  $p--; # Counter after password
  $m[$p]--; # --
  $p++;$p++; # First char
  print chr $m[$p]; # print it
# print $m[$p], ' '; # print non-ascii values in debugging
  $m[$p] = new Eightbit(0);
  $p++; # next
};

};

__END__

1.3 Understanding

Ok, let me explain that.
First, here's how the total program works in Perl pseudocode

print "PW: ";
my $pass = <STDIN>;
if (hash($pass) != 128) { 
    destroy_data(); 
    print "WRONG"; 
}
else {
    my $ciphertext = ciphertext();
    my $plaintext = decrypt($pass, $ciphertext);
    print $plaintext;
}

We are provided with a ciphertext, we provide a password, and it decrypts it
according to the password. The block above takes the first character of the
password, subtracts that from the first character of the string, then 
removes that character of the string and moves on to the next, and copies that
first character of password to the end of the password. So the password
rotates, such as:

abcdef -> bcdefa -> cdefab

And we keep going until we have exhausted the ciphertext

What is this? It's a Vigenere cipher! A Vigenere cipher is a series of shift
ciphers, so if you chose a password like "caesar", then the first character of
your ciphertext would be the sum of the first character of your plaintext and
'c'. The second character of the ciphertext is the second character of your
plaintext added with 'a'. When you run through the passphrase, you just start
at the beginning again. The ciphertext is the same length as the plaintext,
with a one-to-one character correspondence. The Vigenere cipher is a simple
stream cipher, and there are many weaknesses in it.

I conveniently have code to pwn those! See rattle's first crypto challenge at
http://www.awarenetwork.org//crypt0/vigenere/

Except, I don't think it will work. Maybe not.

Vigenere is easier to break the longer the text is, and the bigger the
text:password length ratios. We have a 61 character ciphertext. The password
better not be fucking 40 characters again. That would be unbreakable by
Kasiski or Z (hehe) methods



--[ 02 ]------------------------------------------------[ Wordlist Attack ]-----


Using a wordlist is a good place to start. About 1/256 of possible phrases will
work (because the hash result is stored as an eightbit value), so if you have 
sizable wordlists then this is definitely worth a shot. First, trim your 
wordlists down to size.

2.1 filter.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <errno.h>

#define MAX_LEN 30

void transform(char*);
int valid_hash(const char*);
uint16_t line_length(const char*);
void usage();

int main(int argc, char **argv)
{
    char buffer[MAX_LEN + 2];
    FILE *in_fh, *out_fh;

    if (argc < 3) usage();

    if ( (in_fh = fopen(argv[1], "rb")) == NULL )
    {
        perror("Input file");
        exit(EXIT_FAILURE);
    }

    if ( (out_fh = fopen(argv[2], "w")) == NULL )
    {
        perror("Output file");
        exit(EXIT_FAILURE);
    }

    while ( fgets(buffer, MAX_LEN, in_fh) != NULL )
    {
        transform(buffer);
        if ( valid_hash(buffer) )
        {
            if ( fputs(buffer, out_fh) == EOF )
            {
                puts("File printing error");
                fclose(out_fh);
                exit(EXIT_FAILURE);
            }
        }
    }

    fcloe(in_fh);
    fclose(out_fh);

    return(EXIT_SUCCESS);
}

void transform(char *buffer)
{
    int32_t length = line_length(buffer);
    buffer[length] = '\n';
    buffer[length+1] = 0;
}

int valid_hash(const char* buffer)
{
    if (!buffer) return 0;
    uint8_t total = 0;

    int32_t pos = line_length(buffer) - 1;
    if (pos <= 0) return 0;

    while ( pos >= 0 )
    {
        total += buffer[pos] * 2;
        --pos;
        if (pos < 0) break;
        total -= buffer[pos];
        --pos;
    }
    return total == 128;
}

uint16_t line_length(const char* buffer)
{
    unsigned int pos = 0;
    while ( buffer[pos] != '\n' && buffer[pos] != '\r'
        && buffer[pos] != 0 ) ++pos;
    return pos;
}

void usage()
{
    puts("./chall4 inputfile outputfile");
    exit(EXIT_FAILURE);
}

2.2 Results

I used the above code to generate a wordlist. I basically put all of my
translated program into a subroutine and then did this:

while (my $word = <$fh>)
{
    my $temp = compute($word);
    $temp =~ /aware|mortal|rattle|penis/i and print "Success: $word";
    $temp =~ /[Tt]he/ and print "Lesser success: $word"; 
}

A temporary variable is good because the actual computation is very expensive.
Twenty $m[$p]++ in a row is a series of operations, while $m[$p] += 20 would be
a little more atomic by Perl standards. Plus it's just a lot of stuff happening,
and all happening in Perl. Not to mention it's all happening on an overloaded 
object.

Using C would be more efficient, but really was not worth it after I had my Perl
generated. Considering you end up with a shortened wordlist, this does not take
too long. Now if I was going to bruteforce, then I would want to lose Perl.

By the way, I do not chomp($word) before running it through compute(), because
the newline is needed at the end. That is also convenient for my output.

Unfortunately, I had no success. I lacked the necessary word or phrase.



--[ 03 ]--------------------------------------------------[ Cryptanalysis ]-----


The trick to beating a Vigenere cipher is to find the length of the password.
Once you have that, then you just have a series of Caesar ciphers. A Caesar
cipher is just a cipher where the alphabet has been shifted, such as rot13
encoding. To find out the shift, you just assume that the most common character
is a space (or an 'e', or whatever the appropriate character is) and then you've
found the shift. The Vigenere cipher is stronger than a simple Caesar cipher not
only because you have to find out the passphrase length, but also because it
gives you a series of smaller shift ciphers ( n / length(passphrase) ) to work
with.

To find the length, there is the traditional Kasiski method, and then there is
the method I used successfully last time.

3.1 Kasiski Method

The Kasiski method is to find repeated substrings. These suggest that the
password has overlapped the same plaintext at the same period in the password
rotation. This is very possible given common English words like "the" and such,
and is compounded by the shortness of the password. For reoccurances that are
not coincidences, the length between them will be some multiple of your
password length.

Imagine you have an 18 character password. Somehow your ciphertext has some term
repeated twice. The second time it happens, that *could* be with a completely
different plaintext, just with a different part of the password. Or it could be
the same plaintext, which only turns out to be the same ciphertext when that
plaintext is ciphered against the same part of the password. 

Imagine the repeated string is 195 227 194 218 208. This might have happened
because of the following situation, where the password is 'blackhats'.

aware is aware.
blackhatsblackh

The string 'aware' perfectly overlaps with 'black' twice, creating the same
ciphertext in both occasions. As I said before, this could happen randomly,
with random plaintexts on different part of the password. The longer your 
repeated string is, the less likely it's random. A lot of two-character 
repetitions can be ignored, and probably should be if you have anything longer
to work with.

This tells us something. If we look at the difference in space between the two
repeated strings, we would see that they are nine characters apart. They are
nine characters apart because that is the length of the password, it's only at
nine (or eighteen or twenty-seven or other multiples of nine) that the password
repeats itself.

This is a fake example. In reality, if the term 'aware' is repeated enough and
you get one or more repetitions in your ciphertext, they could be quite apart.
They could be 72 characters apart, for example. If they were 72 characters
apart, then we could guess that the passphrase is 72 characters long, or 36,
or 24, or 18, or 12, or 9, 8, 6, 4, 3, 2, or 1 characters long. This one
repetition on its own gives us these options (72 has a lot of factors!). What
we do is analyze all large repetitions, aggregate the data, and see what fits.
If there was good repetition that was 81 characters away, we then narrow down
our possibilities to 9, 3, and 1.

Once we have our password length we just split the text into individual Caesar
ciphers and start to break them. We figure out what our likely most common
character is, perhaps space or 'e' or period, and then we use that to find the
shift amount in any given individual Caesar cipher.

However, there are a some issues that could render this ineffective in our
case, and ultimately running the Kasiski method against our ciphertext failed.

As you can see, very few single-character values repeat at all, let alone 
multi-character strings! It's only a 61 character ciphertext!

# The count of any given ciphertext character
$VAR1 = {
      '204' => 1,
      '206' => 2,
      '198' => 3,
      '227' => 1,
      '200' => 2,
      '162' => 1,
      '147' => 1,
      '156' => 1,
      '218' => 1,
      '168' => 1,
      '215' => 2,
      '201' => 1,
      '145' => 1,
      '224' => 1,
      '148' => 1,
      '223' => 1,
      '217' => 1,
      '158' => 2,
      '205' => 2,
      '212' => 4,
      '219' => 1,
      '214' => 1,
      '157' => 1,
      '149' => 1,
      '197' => 1,
      '221' => 1,
      '203' => 1,
      '210' => 3,
      '213' => 2,
      '199' => 4,
      '146' => 3,
      '160' => 2,
      '153' => 1,
      '211' => 4,
      '209' => 3,
      '196' => 2,
      '195' => 1
    };

203 224 217 209 168 146 (158 199) 209 200 (205 211) 196 221 199 212 146
212 213 211 148 195 160 146 227 214 198 198 215 196 197 218 145 223 204
213 162 (210 206) (205 211) 160 157 147 199 149 153 201 198 219 210 (158
199) 212 209 (210 206) 200 156 211 215 212

There are no long repeated substrings. Three two-character strings repeat
twice:

205 211 : 29 : (1) 29
210 206 : 18 : (1) 2 [3] 6 {9} 18
158 199 : 45 : (1) [3] 5 {9} 15 45

1, 3, and 9 are the best potential password lengths. But make no mistake,
these could be coincidences.

3.2 Z Method

What I do is take potential lengths (like 5-20), and find out how unbalanced the
character distribution would be if the password was that length. If it is the
wrong length, we will find the distribution balancing down. If it is the right
length, the common letters (like 'e') will be much more common in our resulting
plaintext.

The way I actually did this in the challenge was to generate the Caesar ciphers
for any given length. Then for each cipher, I just added the count of the most
common plaintext character. Add the counts from all the shift ciphers, and I get
a score for any given length. This is not the best way to incorporate all
information about distribution, but it worked. I also did not necessarily score
it in the most effective way, so I implemented a few methods.

If you guess the length right, you will find many duplicate characters. For
example, say we have individual Caesar ciphers with 80 items, after guessing the
right length. Maybe in a given one, 10 of those 80 chars are the same. That is,
they are the same because they are all supposed to be spaces, and since they are
all in the same shift cipher they have all been shifted by the same amount. It
does not really matter whether these characters are all spaces or 'e's or
anything in particular, what matters is how noticable they are.

On the other hand, if we had the wrong length, we'll just have a somewhat random
distribution. The ciphertext characters will not match up correctly with the
other ones that are shifted by the same amount, and our duplicates will be
distributed to different shift ciphers. This means that we will not have as many
duplicates in any given shift cipher, at least it is not as likely.

Here, from rattle's earlier Vigenere challenge, the distribution up to 50
characters.

Length: 1 |-| Sum: 253
Length: 2 |-| Sum: 278
Length: 3 |-| Sum: 256
Length: 4 |-| Sum: 288
Length: 5 |-| Sum: 343 <-- Jump!
Length: 6 |-| Sum: 283
Length: 7 |-| Sum: 270
Length: 8 |-| Sum: 369 <-- Jump!
Length: 9 |-| Sum: 261
Length: 10 |-| Sum: 483 <-- Massive jump!
Length: 11 |-| Sum: 273
Length: 12 |-| Sum: 300
Length: 13 |-| Sum: 279
Length: 14 |-| Sum: 295
Length: 15 |-| Sum: 360 <-- Jump
Length: 16 |-| Sum: 390
Length: 17 |-| Sum: 272
Length: 18 |-| Sum: 291
Length: 19 |-| Sum: 279
Length: 20 |-| Sum: 728 <-- Massive jump!
Length: 21 |-| Sum: 290
Length: 22 |-| Sum: 296
Length: 23 |-| Sum: 291
Length: 24 |-| Sum: 393 <-- Jump!
Length: 25 |-| Sum: 366
Length: 26 |-| Sum: 310
Length: 27 |-| Sum: 291
Length: 28 |-| Sum: 318
Length: 29 |-| Sum: 286
Length: 30 |-| Sum: 506 <-- Jump!
Length: 31 |-| Sum: 304
Length: 32 |-| Sum: 419
Length: 33 |-| Sum: 311
Length: 34 |-| Sum: 322
Length: 35 |-| Sum: 382
Length: 36 |-| Sum: 332
Length: 37 |-| Sum: 322
Length: 38 |-| Sum: 329
Length: 39 |-| Sum: 315
Length: 40 |-| Sum: 1209 <-- Super huge crazy massive jump!
Length: 41 |-| Sum: 313
Length: 42 |-| Sum: 336
Length: 43 |-| Sum: 322
Length: 44 |-| Sum: 362
Length: 45 |-| Sum: 400
Length: 46 |-| Sum: 346
Length: 47 |-| Sum: 339
Length: 48 |-| Sum: 442
Length: 49 |-| Sum: 329
Length: 50 |-| Sum: 532

The values get higher as you go (quite naturally) but we are looking for
big jumps. I pointed out some. As you can see, 40 characters is the winner
by far, and its factors of 20, 10, 8, and 5 had big jumps as well. The
jump gets bigger (both in change and proportion) the larger the factor.

So, here is the analysis for our small ciphertext:

Length: 1 |-| Sum: 4
Length: 2 |-| Sum: 7
Length: 3 |-| Sum: 6
Length: 4 |-| Sum: 9
Length: 5 |-| Sum: 10
Length: 6 |-| Sum: 10
Length: 7 |-| Sum: 11
Length: 8 |-| Sum: 13
Length: 9 |-| Sum: 15
Length: 10 |-| Sum: 12
Length: 11 |-| Sum: 14
Length: 12 |-| Sum: 15
Length: 13 |-| Sum: 14
Length: 14 |-| Sum: 14
Length: 15 |-| Sum: 18
Length: 16 |-| Sum: 19
Length: 17 |-| Sum: 20
Length: 18 |-| Sum: 22
Length: 19 |-| Sum: 23
Length: 20 |-| Sum: 21
Length: 21 |-| Sum: 23
Length: 22 |-| Sum: 24
Length: 23 |-| Sum: 25
Length: 24 |-| Sum: 26
Length: 25 |-| Sum: 25
Length: 26 |-| Sum: 26

The rest (up to 62) are all one or zero sum jumps.

Note that a 62-character password will never have its 62nd character used
against the 61-character ciphertext. It would be a one-time pad.

A 30 character passphrase would find every character used twice, which would
tell us nothing.

Part of me likes to imagine that rattle would give us a chance on this.
Something less than 30.

Well, what do we have? No massive peaks. The only jumps that even get out of
order at all are 2 and 9, with a respectable jump at 15.

So what can I say? Both methods concur for 9, but we really do not have much on
it. The reason they concur is not a coincidence, in this situation they are
almost measuring the same thing.

3.3 Analysis

Assuming a nine-character password:

     Individual Caesar Ciphers
 1    2    3     4    5    6    7    8    9
203  224  217   209  168  146 (158  199) 209 
200 (205  211)  196  221  199  212  146  212 
213  211  148   195  160  146  227  214  198
198  215  196   197  218  145  223  204  213 
162 (210  206) (205  211) 160  157  147  199 
149  153  201   198  219  210 (158  199) 212 
209 (210  206)  200  156  211  215  212

Range of values:
 64   62   69    14   65   66   70   68   15

Distance between smallest and next smallest:
 13   52   48    01   04   01   01   01   01

Distance between highest and next highest:
 04   14   06    04   02   01   04   02   01

Range of potential characters (Nothing smaller than 32 or higher than 122):
  1    2       3       4       5       6        7       8       9
91-117  102-121  95-116  87-163  99-124  89-113  105-125  90-114  91-166

Good news! These ranges tell us that there could be some high uppercase 
(W at worst), all the way up to two possible extremities (163,166). If we put
an upper limit of 126 on these, and get a range of 87-126, these 39 positions
include all 26 lowercase letters. What does this mean? It means we might be
looking at an entirely lowercase password. This is, of course, assuming that
rattle did not make use of the full eightbit space.

Could I be wrong? Absolutely. One or more of these could hold characters
smaller than 32, such as a newline.

There are also no overflowing results. Seems like mostly alphanumberic text
ciphered with an alphanumeric passphrase.

Columns six, seven, and eight all have low bottoms, and then values one higher
than that. What low consecutive ASCII characters could be used? Space and
exclamation mark?

One thing I was hoping for was for the last letter in the plaintext to be a
period. No such luck, or at least not with a nine-character passphrase.

The ciphertext is too short to contain multiple sentences, so there should not
be excessive punctuation. Just one sentence, so the low two characters in those
three columns might not be the exclamation mark and space. If they were dash
and period, we would get this:

 1    2    3     4    5    6    7    8    9
203  224  217   209  168   .  (      b ) 209 
200 (205  211)  196  221   c    d    -   212 
213  211  148   195  160   .    r    q   198
198  215  196   197  218   -    o    g   213 
162 (210  206) (205  211)  2    -    199 
149  153  201   198  219   n  (      b ) 212 
209 (210  206)  200  156   m    g    o

That looks blatantly wrong, as did a couple of other things I checked.

3.4 Alternative

Something I wanted to do, but ended up not doing, was to use a scoring system
and rank different potential passwords. I'd call it a z-score for ciphers, just
to mess with you. It has nothing to do with statistical z-scores.

The idea is that we measure the goodness of fit of a password. We create an
acceptable list of characters that we could expect in the plaintext, including
letters, numbers, punctuation, etc. Then we calculate the percentage of
resulting characters that are within that character set for a given password.
So if a password resulted in an entirely alphanumeric plaintext, the score
would be 100. Another password that gave us 59 alphanumeric characters out of
61 would have a score of 59/61 = 97.

The point is that we can rank potential passwords according to this score. Even
if we do not have the correct password at any point, if we get enough characters
right then that will be reflected in the score. Calculate the scores through a
wordlist or as you bruteforce, and watch the top. You have a good chance of
learning part of the password.



--[ 04 ]-----------------------------------------[ Known Plaintext Attack ]-----


4.1 Motivation

Originally I expected this to be a sentence, such as an IRC quote. I even
wondered if it could be the very sentence that was the passphrase last time. I
checked that. There are a few very different low-ASCII values, and having a 
single sentence with limited punctuation just did not make sense.

Eventually it hit me: this could be a URL. If the plaintext started with "www",
we could figure this out trivially! It didn't, because then the fourth value
(209) would have to represent a period, and since 209 was the largest value in
that shift cipher, there would be six characters with lower ASCII values. Could
it start with "http://"? It just might! That looked like it made sense, except
possibly for that fourth character. Was 'p' likely to be the highest ASCII
character out of seven?

Since I had doubt, I really did not want to do all of it by hand. So I wrote
this script for decyphering a Vigenere cipher with some known plaintext and
known key length.

4.2 kpt.pl

#!/usr/bin/perl

use strict;
use warnings;

my @ciph = qw/
203  224  217  209  168  146  158  199  209
200  205  211  196  221  199  212  146  212
213  211  148  195  160  146  227  214  198
198  215  196  197  218  145  223  204  213
162  210  206  205  211  160  157  147  199
149  153  201  198  219  210  158  199  212
209  210  206  200  156  211  215  212
/;

my ($kpt, $len, $start) = @ARGV;

unless ( $len ) 
{
    print "perl $0 known-plaintext len <start>\n";
    exit -1;
}

($start ||= 0) <= $#ciph or die "pos out of range\n";

my @kpt = map ord, split '', $kpt;

# Default pass character
my @pass = ('*') x $len;

# Generate the password based on the known plaintext
for my $i ( 0 .. $#kpt )
{
    $pass[($start + $i) % $len] = $ciph[$start + $i] - $kpt[$i];
}

# Print our guessed password
print "Estimated password: ";
for my $val ( @pass )
{
     print $val eq '*' ? $val : chr $val;
}
print "\n";

# Print our plaintext
for my $i ( 0 .. $#ciph )
{
    print $pass[$i % $len] ne '*' 
        ? chr($ciph[$i] - $pass[$i % $len]) : '*', '';
    $i % $len  == $len - 1 and print "\n";
}
print "\n";


4.3 Results

zshzn@grapevine:~$ perl kpt.pl http:// 9
Estimated password: cleanco**
h t t p : / / * * 
e a n c o d e * * 
r g / b 2 / t * * 
c k _ d l . p * * 
? f i l e = . * * 
2 - d e m o / * * 
n f i g . p h * 

There we have it, and the rest of the password is even in that plaintext:
cleancode.

The solution: http://cleancode.org/b2/track_dl.php?file=./b2-demo/config.php



--[ 06 ]----------------------------------------------------[ Conclusions ]-----


I certainly underestimated the known plaintext attack at the beginning. Not
only could I accurately guess part of the plaintext, I could have written
code to rotate a guessed string (like "php" for example) and find where an
estimated plaintext fit in.

One thing that would have made it that much more challenging would have been
base64 encoding. But as it was, it was a pretty diverse set of characters in
the plaintext. Sure wasn't a simple space-based sentence like traditional
examples. Any kind of unknown encoding before ciphering would have made this
much more difficult, especially anything that integrates across the plaintext.
Might as well not bother using a Vigenere cipher at all then.

There really is very added little security in using a Vigenere cipher. Sure it
took work, but I did eventually beat it. Password length, or more accurately
(ciphertext length / password length), is a crucial determinant of the security
level. A ratio of seven is much too high. If it was three, i.e. a twenty-
character passphrase, then knowing seven bytes would only have revealed a
third of the text, leaving much work to do. That's still horrible. Ultimately
a Vigenere cipher is only as useful as the degree to which it is a one-time
pad.

--------------------------------------------------------------------[ EOF ]-----
This page is part of the .aware network. Content and design © 2004 - 2014 .aware network
Due to certified insanity, we are not responsible for anything, period.