Page 1 of 1

Insert Character - String

Posted: Fri Aug 27, 2010 7:41 am
by timWebUK
I've got a string containing a 56-bit binary number. I'm trying to write a piece of PHP that will insert a 0 *after* every 7th bit. Increasing the binary string to 64bits at the end of it.

This is what I have so far...

Code: Select all

for($i = 0; $i < 63; $i++)
		{
			$binArray[$i] = $binData{$i};
			if($i % 7 == 0)
			{
				$i++;
				$binArray[$i] = '0';
			}			
		}
But this isn't working because of the logic I've used, I just can't seem to figure it out. My initial idea being, move a bit at a time from the string to an array, inserting a 0 after every 7th bit, then converting that array into a string. If anyone could give me hand, I'd be hugely grateful.

Re: Insert Character - String

Posted: Fri Aug 27, 2010 9:38 am
by Apollo
Several mistakes:
  • By doing $i++ in the ($i%7==0) condition, you skip those $binData[$i] bits
  • You're generating a total of 63 bits in the output (not 64)
  • You're reading $binData[$i] for $i>=56 while $binData contained only 56 bits?
  • The ($i %7 == 0) condition is already true in the first iteration (when $i==0), while it should occur after the 7th bit for the first time
From what you describe, this seems easier to me:

Code: Select all

$output = '';
for($i=0; $i<8; $i++) $output .= substr($binData,$i*7,7).'0';

Re: Insert Character - String

Posted: Fri Aug 27, 2010 10:05 am
by AbraCadaver
Without a loop for fun:

Code: Select all

$binData = implode('0',array_map('implode',array_chunk(str_split($binData),7))).'0';

Re: Insert Character - String

Posted: Fri Aug 27, 2010 10:15 am
by timWebUK
Thanks for the analysis. That was really helpful. Your code worked fine as well, as expected!

However I have run into an issue I did not expect, when using base_convert to convert my hexadecimal number into binary, I lose a bit. Causing my binary number to be 55 bits, and the result of that 63 bits.

A useless number that can't be successfully converted into anything. Can anyone shed any light as to why I might lose a bit when using base_convert?

Code: Select all

$binDataA = base_convert($hexDataA, 16, 2);	
Using base_convert($string, 16, 16); produced the following interesting result:

50454e5449554d
50454e5449554c

As you can see, it decrements the last character.

Re: Insert Character - String

Posted: Fri Aug 27, 2010 10:31 am
by AbraCadaver
timWebUK wrote:Thanks for the analysis. That was really helpful. Your code worked fine as well, as expected!

However I have run into an issue I did not expect, when using base_convert to convert my hexadecimal number into binary, I lose a bit. Causing my binary number to be 55 bits, and the result of that 63 bits.

A useless number that can't be successfully converted into anything. Can anyone shed any light as to why I might lose a bit when using base_convert?

Code: Select all

$binDataA = base_convert($hexDataA, 16, 2);	
Using base_convert($string, 16, 16); produced the following interesting result:

50454e5449554d
50454e5449554c

As you can see, it decrements the last character.
Not sure without seeing the numbers, but try:

Code: Select all

$binData = sprintf('%056b', $hexData);

Re: Insert Character - String

Posted: Fri Aug 27, 2010 10:38 am
by timWebUK

Code: Select all

<?php
//Windows LM Hash Generator

	// Constants
	define("NULLCHAR", "\0");
	define("ASCII", 'KGS!@#$%');
		
	// Get Sample Password
	$pass = $_GET['pass'];
	
	// Convert to uppercase
	$pass = strtoupper($pass);
	
	// Pad to 14 bytes
	$pass = str_pad($pass, 14, NULLCHAR);
	
	// Split into two 7 byte strings
	$words = str_split($pass, 7);	
	$halfA = $words[0];
	$halfB = $words[1];
	
	echo 'Part A length: ' . strlen($halfA) . '<br />';
	echo 'Part B length: ' . strlen($halfB) . '<br />';
	
	// Generate DES Keys from two halves
	
		// Half A
		$hexDataA = bin2hex($halfA);
		echo 'Part A Hex: ' . $hexDataA . '<br />';
		$binDataA = base_convert($hexDataA, 16, 2);			
		echo 'Part A Binary: ' . $binDataA . ' (' . strlen($binDataA) . ' bits)<br />';
		
		$keyA = '';
		for($i = 0; $i < 8; $i++) 
		{
			$keyA .= substr($binDataA, $i*7, 7) . '0';
		}
		
		echo $keyA . ' (' . strlen($keyA) . ' bits)<br />';
		
		// Half B
		$hexDataB = bin2hex($halfB);
		echo 'Part B Hex: ' . $hexDataB . '<br />';
		$binDataB = base_convert($hexDataB, 16, 2);			
		echo 'Part B Binary: ' . $binDataB . ' (' . strlen($binDataB) . ' bits)<br />';
		
		$keyB = '';
		for($i = 0; $i < 8; $i++) 
		{
			$keyB .= substr($binDataB, $i*7, 7) . '0';
		}
		
		echo $keyB . ' (' . strlen($keyB) . ' bits)<br />';
		

		
	// Encrypt ASCII constant with DES Encrypt against keys
	
	// Concatenate the results - the LM Hash


?>
This is what I have so far. I'm working implementing the Windows LM Hash Algorithm just for a bit of fun. Proving awkward so far! Ran into a few issues so far, including if the password isn't more than 7 characters long, then it doesn't create the NULL bit stream properly.

The code you posted produced the following:
00000000000000000000000001111111111111111111111111111111

Re: Insert Character - String

Posted: Fri Aug 27, 2010 10:01 pm
by McInfo
If you don't like spoilers, stop reading now.

My (partial) solution uses an array of 8-bit numbers rather than a string of 0s and 1s. It uses bitwise operators to shift bits and to grab an overflowed bit that will move to the next byte.

I'm not sure that I shifted the bits in the correct direction. I just made a guess based on what I read in the Wikipedia article on LM hash. If I'm wrong, it wouldn't be too difficult to swap the bit-shift operators (<<, >>) and grab the high bit (& 128) instead of the low bit (& 1).

I got only as far as generating the DES keys. I did not implement the DES encryption nor actually generate the LM hash.

Code: Select all

<?php
header('Content-Type: text/plain');

/*
 * LAN Manager Hash Algorithm (From http://en.wikipedia.org/wiki/LM_hash)
 *
 * 1. The user’s ASCII password is converted to uppercase.
 * 2. This password is null-padded to 14 bytes.[Notes 1][3]
 * 3. The “fixed-length” password is split into two 7-byte halves.
 * 4. These values are used to create two DES keys, one from each 7-byte
 *    half, by converting the seven bytes into a bit stream, and
 *    inserting a null bit after every seven bits (so 1010100 becomes
 *    01010100). This generates the 64 bits needed for the DES key.
 * 5. Each of these keys is used to DES-encrypt the constant ASCII
 *    string “KGS!@#$%”, resulting in two 8-byte ciphertext values. The
 *    DES CipherMode should Set to ECB, and PaddingMode should set to
 *    NONE.
 * 6. These two ciphertext values are concatenated to form a 16-byte
 *    value, which is the LM hash.
*/

// Example password input
$x = 'samplepwd';

// 1. Converts password to uppercase; limits password length to 14 bytes
$x = strtoupper(substr($x, 0, 14));

// 2. Null-pads password to 14 bytes
$x = str_pad($x, 14, "\0", STR_PAD_RIGHT);

// 3. Splits password into two 7-byte halves
$x = str_split($x, 7);

// 4. Splits the halves into arrays of numeric ASCII values
$x[0] = array_map('ord', str_split($x[0], 1));
$x[1] = array_map('ord', str_split($x[1], 1));

// Adds an 8th byte to each array for the 7th byte to overflow into
$x[0][] = 0;
$x[1][] = 0;

// Displays the original, unshifted bytes as base-10 numbers
print_r($x);
echo PHP_EOL;

// For both halves
for ($i = 0; $i < 2; ++$i) {

    // Displays a heading
    printf('--Half %u--%sInitial: ', ($i + 1), PHP_EOL);

    // Displays the initial binary state of all 8 bytes
    for ($j = 0; $j < 8; ++$j) {
        printf('%08s ', decbin($x[$i][$j]));
    }
    echo PHP_EOL;

    // Binary string representation of 64-bit DES key
    $desKey = '';

    // For all 8 bytes
    for ($j = 0; $j < 8; ++$j) {

        // Captures the smallest bit and shifts it to prepare it
        // to be moved into the largest position in the next byte
        $overflow = (($x[$i][$j] & 1) << 8);

        // Shifts the bits in this byte to drop the smallest bit
        // and gain a 0 in the largest position
        $x[$i][$j] = ($x[$i][$j] >> 1);

        // Displays a line label
        printf('Shift %u: ', ($j + 1));
        
        // Loops over all 8 bytes again
        // If not for printf(), $k could start at $j+1
        // This loop cascades the shift to the remaining bytes
        for ($k = 0; $k < 8; ++$k) {

            // Because $k starts at 0, this condition is needed
            if ($k > $j) {

                // Adds the overflow bit from the previous byte,
                // temporarily making this byte 9 bits long
                $x[$i][$k] += $overflow;

                // Captures the smallest bit from this byte and
                // shifts it to prepare it to be moved to the high
                // position in the next byte
                $overflow = (($x[$i][$k] & 1) << 8);

                // Shifts this byte, dropping the smallest bit and
                // returning the length of this byte to 8 bits
                $x[$i][$k] = ($x[$i][$k] >> 1);
            }

            // Displays this byte, padded with 0s to 8 bits
            printf('%08s ', decbin($x[$i][$k]));
        }

        // Appends this byte to the DES key
        $desKey .= sprintf('%08s', decbin($x[$i][$j]));

        echo PHP_EOL;
    }
    echo PHP_EOL;

    // Displays the full DES key
    printf('DES Key %u: %s', ($i + 1), $desKey . PHP_EOL . PHP_EOL);
    
    // Merges numbers into a single 64-bit DES key
    // (likely to work on 64-bit operating systems)
    /*
    $x[$i] = (
        ($x[$i][7] <<  0) +
        ($x[$i][6] <<  8) +
        ($x[$i][5] << 16) +
        ($x[$i][4] << 24) +
        ($x[$i][3] << 32) +
        ($x[$i][2] << 40) +
        ($x[$i][1] << 48) +
        ($x[$i][0] << 56)
    );
    */
}

// Displays the resulting shifted bytes as base-10 numbers
print_r($x);

// 5. (not implemented)
// 6. (not implemented)
Edit: Appended the 8th byte to the DES key.
Edit: Really fixed the 8th byte problem.

Re: Insert Character - String

Posted: Fri Aug 27, 2010 10:05 pm
by AbraCadaver
Wow! Have a life much? :wink:

Re: Insert Character - String

Posted: Fri Aug 27, 2010 11:07 pm
by McInfo
AbraCadaver wrote:Wow! Have a life much? :wink:
Everybody has a life. I just choose to devote a lot of mine to finding solutions to interesting puzzles. The only problem is that nobody pays me for it.

Re: Insert Character - String

Posted: Sat Aug 28, 2010 10:57 am
by McInfo
My second solution is 35% or more faster than my first solution, and it's probably a little easier to follow, but it's not as cool as bit shifting.

Code: Select all

<?php
header('Content-Type: text/plain');

// Example password input
$x = 'samplepwd';

// Limits password length to 14 bytes
$x = substr($x, 0, 14);

// Converts password to uppercase
$x = strtoupper($x);

// Null-pads password to 14 bytes
$x = str_pad($x, 14, "\0", STR_PAD_RIGHT);

// Converts string into array of characters
$x = str_split($x, 1);

// Converts characters to 8-bit binary
function charTo8BitBinary ($c) {
    return sprintf('%08s', decbin(ord($c)));
}
$x = array_map('charTo8BitBinary', $x);

// Converts the array to a string
$x = implode('', $x);

// Spits the string into an array of 7-bit chunks
$x = str_split($x, 7);

// Rejoins the chunks, inserting a zero before each chunk
$x = '0' . implode('0', $x);

// Splits the string into two halves
$x = str_split($x, 64);

// Displays the two DES keys
var_dump($x);

Re: Insert Character - String

Posted: Tue Sep 07, 2010 11:38 am
by timWebUK
Thanks for the interesting solution... however, I would quite like to carry on implementing the solution the way I initially set out!

If anyone could provide any insight as to why I get the strange output, I'd be grateful.