Rainbow Table: Unable to get last reduction

Question

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 qt4.7 (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?

Whiplash

Answer 1

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:

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.

Solitaire

Why the image you add is not found? I dont fully understand your answer yet. Doest it mean that the accepted answer on the link I post is incorrect? – Whiplash

Image loads fine for me. The linked answer is not incorrect per se, I'd say it just needs a little added clarification. The general idea is correctly explained, the little caveat that not every chain always hits its input value again is missing. – Solitaire

This is the link of the image right? i.sstatic.net/sh0F4.png it says 404 not found I'm using linux and tried to open this on windows but still not found. Anyway on the code that I did what are the things should I change? or it is impossible to achieve my goal because I'm using md5 as an example? – Whiplash

Image was taken from here, is this better? security.stackexchange.com/a/10661 – Solitaire

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. – Solitaire

I could see the image now at home pc. So it means that I should change the reduction function like getting the 2nd number to 6th instead of 1st to 5th number? I thought the reduction function is always getting the first digit up to the guessed length of password. ( When the password contain only numeric digits. – Whiplash

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 99999 → 00000 again (you actually expect the path to be more random looking than that, but it's the same principle). (continued...) – Solitaire

... Well, that's not happening. It's going 00000 → 00001 → 00002 → 00001 → 00002... 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. – Solitaire

@abi Oops, typo'd a 0... Pedant of the week award to you. ;) – Solitaire