Create a gist now

Instantly share code, notes, and snippets.

@carnage /breaker.php Secret
Created Aug 8, 2015

Class which breaks hashids encoding
<?php
class Breaker
{
const ONLY_PRINTABLE = 1;
private $lowerLimit = 0;
private $upperLimit = 256;
public function __construct($flags = 0)
{
if ($flags & self::ONLY_PRINTABLE) {
$this->lowerLimit = 32;
$this->upperLimit = 127;
}
}
private function swap(&$alphabet, $i, $j)
{
$temp = $alphabet[$j];
$alphabet[$j] = $alphabet[$i];
$alphabet[$i] = $temp;
}
private function findNextCharacters(array $salt, $outputIndex, $inputIndex)
{
$t = 0;
foreach ($salt as $s) {
$t = ($t + $s) % $outputIndex;
}
$return = [];
for ($i = $this->lowerLimit; $i < $this->upperLimit; $i++) {
$test = $t + $i+ $i + count($salt);
if (($test % $outputIndex) === $inputIndex) {
$return[] = $i;
}
}
return $return;
}
private function checkSalt(array $salt, $outputIndex, $inputIndex, $length, $debug = false)
{
$t = 0;
$saltIndex = 0;
for ($i = 0; $i < $length; $i++) {
$saltIndex = $i % count($salt);
$t = ($t + $salt[$saltIndex]) % $outputIndex;
}
$t += $salt[$saltIndex] + $saltIndex;
return (($t % $outputIndex) === $inputIndex);
}
public function findSalt($inputString, $outputString, $limit = 10)
{
$initialOutputIndex = strlen($inputString) - 1;
$outputOffset = strlen($inputString) - strlen($outputString);
$iterations = $initialOutputIndex - $outputOffset;
$iterationLimit = $iterations - $limit + $outputOffset;
$inputStringArray = str_split($inputString);
$terminals = [];
$stack = [[]];
$length = 0;
for ($outputIndex = $initialOutputIndex; $outputIndex > $iterationLimit; $outputIndex--) {
$tStart = microtime(true);
$target = array_search($outputString[$outputIndex-$outputOffset], $inputStringArray, true);
$length++;
$terminalsPassed = [];
foreach ($terminals as $key => $test) {
if($this->checkSalt($test, $outputIndex, $target, $length, ($key === 0))) {
$terminalsPassed[] = $test;
}
}
$terminals = $terminalsPassed;
$strings = [];
foreach ($stack as $salt) {
$chars = $this->findNextCharacters($salt, $outputIndex, $target);
foreach ($chars as $char) {
$string = $salt;
$string[] = $char;
$strings[] = $string;
$terminals[] = $string;
}
}
$stack = $strings;
$this->swap($inputStringArray, $target, $outputIndex);
echo sprintf("Loop %d Took: %.2f \n", $length, (microtime(true) - $tStart));
echo sprintf(
"Found %d new candidate salts, confirmed %d previous salts as still possible\n",
count($strings),
count($terminalsPassed)
);
}
}
}
$b = new Breaker(1);
$b->findSalt('abdegjklmnopqrvwxyzABDEGJKLMNOPQRVWXYZ1234567890', 'OXdwnqJxL41r7zAPpbayY290eNv6ZEBVGlgoQjRDMKW5', 20);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment