Rainbow Table: Unable to get last reduction

Question

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?

deceze · Accepted Answer · 2014-07-09T07:58:28.463

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.

edited Jul 09 '14 at 07:58

answered Jul 09 '14 at 07:39

deceze

510,633
85
743
889

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? – reggie Jul 09 '14 at 07:50
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. – deceze Jul 09 '14 at 07:55
This is the link of the image right? http://i.stack.imgur.com/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? – reggie Jul 09 '14 at 08:50
1

Image was taken from here, is this better? http://security.stackexchange.com/a/10661 – deceze Jul 09 '14 at 08: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 09 '14 at 08:54
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. – reggie Jul 09 '14 at 16:03
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 `99999` → `00000` again (you actually expect the path to be more random looking than that, but it's the same principle). (continued...) – deceze Jul 09 '14 at 16:18
1

... 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. – deceze Jul 09 '14 at 16:20
2

@abi Oops, typo'd a `0`... Pedant of the week award to you. ;) – deceze Jul 09 '14 at 17:14

Rainbow Table: Unable to get last reduction

1 Answers1