6

In this cryptography post it says

The chain can go as long as you want, until it hits the original input. When it hits that point, it will just repeat itself and it will be useless.

So my starting point is 12345 but I can't get the end point and having an endless loop because 12345 doesn't repeat. I'm using (lib version: 4.7.3) to achieve this. Here is my code

rainbowTable::rainbowTable(QWidget *parent) :
QWidget(parent),
ui(new Ui::rainbowTable)
{
    ui->setupUi(this);
    passwordLength = 5;
    qDebug() << getLastReduction("12345",false);
}

QString rainbowTable::hashString(QString value)
{
    QString dataToReturn =  QString(QCryptographicHash::hash((value.toAscii()),QCryptographicHash::Md5).toHex());
    return dataToReturn;
}

QString rainbowTable::reductionOfString(QString hash)
{
    QString dataToReturn = "";
    int iterator = 0;

    while ( iterator < hash.count() )
    {
        if ( hash.at(iterator) == '0' ||
             hash.at(iterator) == '1' ||
             hash.at(iterator) == '2' ||
             hash.at(iterator) == '3' || 
             hash.at(iterator) == '4' ||
             hash.at(iterator) == '5' ||
             hash.at(iterator) == '6' ||
             hash.at(iterator) == '7' ||
             hash.at(iterator) == '8' ||
             hash.at(iterator) == '9' )
        {
            dataToReturn += hash.at(iterator);
            if( dataToReturn.count() == passwordLength )
                break;
        }

        iterator++;
    }

    return dataToReturn;
}

QString rainbowTable::getLastReduction(QString value,bool isHash)
{
    int flagToAvoidImmediateExit = 0;
    if( isHash )
    {
        QString startPoint = value;
        startPoint = reductionOfString(startPoint);

        QString endPoint = "";
        QString tempPoint = startPoint;
        while( startPoint != tempPoint  || flagToAvoidImmediateExit == 0 )
        {
            flagToAvoidImmediateExit = 1;

            endPoint = tempPoint;
            tempPoint = hashString(tempPoint);
            tempPoint = reductionOfString(tempPoint);

            qDebug() << tempPoint;
        }

        return endPoint;
    }
    else
    {
        QString startPoint = value;

        QString endPoint = "";
        QString tempPoint = startPoint;

        while( startPoint != tempPoint  || flagToAvoidImmediateExit == 0 )
        {
            flagToAvoidImmediateExit = 1;

            endPoint = tempPoint;
            tempPoint = hashString(tempPoint);
            tempPoint = reductionOfString(tempPoint);

            qDebug() << tempPoint;
        }

        return endPoint;
    }
}

Here is the debug ouput for a few seconds:

"38064" 
"37923" 
"59636" 
"14842" 
"81105" 
"83011" 
"84978" 
"72903" 
"28301" 
"59067" 
"94222" 
"35329" 
"75907" 
"52980" 
"64297" 
"36654" 
"12207" 
"83738" 
"03523" 
"79083" 
"15597" 
"32652" 
"13934" 
"88497" 
"75435" 
"79791" 
"58265" 
"09856" 
"18041" 
"43966" 
"65978" 
"64242" 
"52739" 
"55704" 
"56811" 
"58183" 
"68597" 
"84064" 
"85717" 
"46438" 
"18042" 
"71321" 
"88067" 
"70648" 
"83580" 
"11878" 
"32297" 
"52376" 
"41289" 
"07909" 
"50439" 
"03819" 
"50325" 
"82736" 
"41621" 
"05497" 
"15546" 
"64017" 
"90503" 
"13150" 
"30287" 
"01749" 
"81308" 
"12036" 
"37241" 
"35850" 
"97225" 
"80539" 
"17472" 
"63098" 
"85818" 
"18438" 
"26139" 
"09545" 
"97042" 
"63672" 
"37406" 
"41180" 
"14910" 
"28900" 
"29729" 
"56861" 
"16208" 
"83565" 
"30912" 
"95541" 
"08468" 
"29539" 
"93679" 
"42487" 
"95833" 
"42793" 
"97064" 
"18087" 
"75623" 
"13910" 
"60404" 
"52557" 
"95932" 
"65477" 
"28304" 
"08456" 
"27849" 
"11429" 
"38896" 
"08634" 
"97107" 
"96385" 
"44159" 
"32875" 
"17063" 
"86213" 
"85052" 
"46852" 
"97541" 
"81412" 
"31199" 
"96618" 
"16178" 
"56100" 
"50394" 
"42087" 
"90552" 
"51966" 
"13598" 
"28757" 
"38715" 
"71025" 
"61334" 
"43686" 
"74633" 
"50360" 
"99883" 
"01361" 
"49662" 
"62929" 
"07280" 
"59161" 
"32509" 
"93670" 
"95649" 
"15206" 
"99927" 
"93692" 
"37748" 
"23350" 
"74680" 
"68259" 
"04819" 
"26627" 
"65968" 
"06919" 
"09194" 
"50084" 
"74452" 
"23763" 
"17953" 
"35026" 
"86691" 
"67542" 
"95634" 
"00793" 
"20270" 
"24386" 
"35606" 
"76055" 
"00010" 
"00798" 
"30867" 
"20697" 
"02143" 
"12044" 
"05098" 
"52828" 
"98446" 
"54039" 
"08778" 
"98405" 
"92267" 
"71783" 
"61953" 
"87447" 
"66505" 
"66535" 
"01776" 
"90120" 
"51497" 
"56082" 
"18253" 
"15222" 
"74769" 
"19614" 
"86376" 
"65391" 
"43365" 
"90484" 
"32717" 
"75052" 
"16186" 
"89444" 
"15439" 
"65166" 
"75785" 
"72462" 
"75920" 
"91383" 
"41678" 
"94123" 
"61751" 
"47976" 
"67798" 
"59438" 
"10180" 
"65854" 
"40218" 
"77990" 
"44843" 
"84554" 
"52350" 
"73347" 
"51901" 
"61155" 
"30316" 
"83096" 
"64946" 
"05985" 
"24208" 
"28718" 
"02241" 
"22303" 
"23331" 
"18410" 
"54868" 
"51723" 
"06401" 
"49554" 
"65577" 
"28105" 
"42319" 
"34167" 
"85036" 
"98679" 
"08594" 
"31075" 
"80514" 
"11517" 
"66780" 
"33411" 
"83180" 
"61910" 
"70423" 
"16885" 
"09107" 
"83702" 
"81842" 
"88430" 
"59146" 
"29140" 
"47236" 
"29625" 
"03078" 
"26540" 
"79321" 
"41649" 
"10210" 
"75702" 
"12020" 
"36877" 
"57307" 
"03222" 
"46603" 
"58449" 
"94709" 
"01436" 
"84975" 
"39385" 
"15952" 
"67607" 
"91666" 
"34456" 
"53385" 
"21512" 
"06712" 
"42073" 
"61343" 
"66825" 
"70199" 
"73203" 
"60216" 
"39469" 
"84324" 
"47850" 
"84825" 
"52471" 
"92397" 
"86051" 
"33676" 
"04221" 
"79740" 
"11573" 
"26304" 
"52510" 
"12679" 
"05930" 
"49607" 
"10880" 
"99174" 
"53967" 
"06397" 
"25700" 
"96721" 
"94694" 
"96566" 
"31746" 
"57359" 
"84870" 
"06236" 
"10673" 
"45914" 
"19209" 
"32478" 
"38824" 
"71178" 
"22983" 
"36320" 
"46594" 
"66538" 
"80495" 
"35645" 
"38064" 
"37923" 
"59636" 
"14842" 
"81105" 
"83011" 
"84978" 
"72903" 
"28301" 
"59067" 
"94222" 
"35329" 
"75907" 
"52980" 
"64297" 
"36654" 
"12207" 
"83738" 
"03523" 
"79083" 
"15597" 
"32652" 
"13934" 
"88497" 
"75435" 
"79791" 
"58265" 
"09856" 
"18041" 
"43966" 
"65978" 
"64242" 
"52739" 
"55704" 
"56811" 
"58183" 
"68597" 
"84064" 
"85717" 
"46438" 
"18042" 
"71321" 
"88067" 
"70648" 
"83580" 
"11878" 
"32297" 
"52376" 
"41289" 
"07909" 
"50439" 
"03819" 
"50325" 
"82736" 
"41621" 
"05497" 
"15546" 
"64017" 
"90503" 
"13150" 
"30287" 
"01749" 
"81308" 
"12036" 
"37241" 
"35850" 
"97225" 
"80539" 
"17472" 
"63098" 
"85818" 
"18438" 
"26139" 
"09545" 
"97042" 
"63672" 
"37406" 
"41180" 
"14910" 
"28900" 
"29729" 
"56861" 
"16208" 
"83565" 
"30912" 
"95541" 
"08468" 
"29539" 
"93679" 
"42487" 
"95833" 
"42793" 
"97064" 
"18087" 
"75623" 
"13910" 
"60404" 
"52557" 
"95932" 
"65477" 
"28304" 
"08456" 
"27849" 
"11429" 
"38896" 
"08634" 
"97107" 
"96385" 
"44159" 
"32875" 
"17063" 
"86213" 
"85052" 
"46852" 
"97541" 
"81412" 
"31199" 
"96618" 
"16178" 
"56100" 
"50394" 
"42087" 
"90552" 
"51966" 
"13598" 
"28757" 
"38715" 
"71025" 
"61334" 
"43686" 
"74633" 
"50360" 
"99883" 
"01361" 
"49662" 
"62929" 
"07280" 
"59161" 
"32509" 
"93670" 
"95649" 
"15206" 
"99927" 
"93692" 
"37748" 
"23350" 
"74680" 
"68259" 
"04819" 
"26627" 
"65968" 
"06919" 
"09194" 
"50084" 
"74452" 
"23763" 
"17953" 
"35026" 
"86691" 
"67542" 
"95634" 
"00793" 
"20270" 
"24386" 
"35606" 
"76055" 
"00010" 
"00798" 
"30867" 
"20697" 
"02143" 
"12044" 
"05098" 
"52828" 
"98446" 
"54039" 
"08778" 
"98405" 
"92267" 
"71783" 
"61953" 
"87447" 
"66505" 
"66535" 
"01776" 
"90120" 
"51497" 
"56082" 
"18253" 
"15222" 
"74769" 
"19614" 
"86376" 
"65391" 
"43365" 
"90484"

As you see 12345 doesn't repeat but other numbers are repeated and having endless loop. Is my starting point wrong?

0

1 Answer 1

24

The chain is not guaranteed to ever hit the initial value again. More often than not you'll probably find it entering a loop like this:

1 -> 2 -> 3 -> 4 -> 2 -> 3 -> 4 -> 2 -> ...

If the input is larger than the hash output, it is impossible by definition to ever hit the initial input value again. However, even if the input has an equal length to the output, it is not guaranteed that the hash will cover every single possible value in the output space before looping around. This actually depends on the characteristics and quality of the hash. A hash may have one big cycle, covering every single possible output value in its loop. Other hashes may enter a number of different possible loops, each covering a different subset of the output space. Other hashes may not ever cover every possible output value.

9
  • 1
    Image was taken from here, is this better? security.stackexchange.com/a/10661
    – deceze
    Jul 9, 2014 at 8:52
  • 4
    It simply means that your reduction function does not equally distribute results over the entire possible spectrum. You'll have to use a different hash/reduction function. I'm no expert in that field to suggest you any specific function, that probably warrants its own question.
    – deceze
    Jul 9, 2014 at 8:54
  • 1
    A hash function has a certain output range. In your case, the output can be 00000, or 00001 or 00002 and so on up to 99999. That's 10000 possible output values. What you're expecting is a loop in those output values. When you input 00000, it'll output 00001. When you input 00001, it'll output 00002 and so on, until you're looped all the way around to 9999900000 again (you actually expect the path to be more random looking than that, but it's the same principle). (continued...)
    – deceze
    Jul 9, 2014 at 16:18
  • 1
    ... Well, that's not happening. It's going 0000000001000020000100002... When you input 00002, it doesn't go to the next "expected" step 00003, it loops back to 00001, from where you're obviously getting into an infinite loop. You'll have to change the fundamental characteristics of your reduction function so it's guaranteed to loop all the way around and not leave out values. It's not about some off-by-one problem, it's the fundamental principle that nothing in your reduction function guarantees a complete loop.
    – deceze
    Jul 9, 2014 at 16:20
  • 2
    @abi Oops, typo'd a 0... Pedant of the week award to you. ;)
    – deceze
    Jul 9, 2014 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.