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?

Re: Insert Character - String
Posted: Fri Aug 27, 2010 11:07 pm
by McInfo
AbraCadaver wrote:Wow! Have a life much?

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.