Rainbow table: it is impossible to get the latest discount

Question

This cryptography post says

The chain can go as long as you want, until it gets to the original input. When he reaches this point, he will simply repeat, and it will be useless.

So, my starting point is 12345 , but I cannot get the end point and have an endless loop, because 12345 not repeated. I am 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 output 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 can see, 12345 does not repeat, but other numbers repeat and have an infinite loop. Is my starting point wrong?

Answer 1

The chain does not guarantee that it will ever hit the initial value again. Most often, you will probably find that it introduces a loop like this:

If the input is larger than the hash output, by definition it is impossible to hit the original input value again. However, even if the input has an equal length for the output, it is not guaranteed that the hash will span every single possible value in the output space before the loop. It actually depends on the characteristics and quality of the hash. A hash can have one large loop spanning every possible output value in its loop. Other hashes may introduce several different possible loops, each of which covers a different subset of the output space. Other hashes may never cover all possible output values.