#21 Hybrid table keyspace broken

closed-wont-fix
James Nobis
None
5
2011-07-13
2010-08-22
No

There's a bug in how the hybrid tables reduction keyspace is allocated. For example, hybrid(loweralpha#6-6,numeric#1-3) is assigned as if it was hybrid(loweralpha#6-6,numeric#0-3), but on reduction the minimum plaintext size is 7.

You can see this for yourself in CChainWalkContext::IndexToPlain() - sometimes nIndexOfX wraps around when m_nIndex is less than pow(26, 6).

Discussion

  • James Nobis
    James Nobis
    2010-08-22

    • assigned_to: nobody --> quelrod
     
  • James Nobis
    James Nobis
    2010-08-22

    Interesting and thanks for investigating it. I know there are fundamental issues with the hybrids and forum discussion on it will reference moving to hybrid2.

    Could you provide a sample hash that shows the problem?

    For md5_hybrid(loweralpha#6-6,numeric#1-3)#0-0_* the md5 of abcdef fails as expected. The md5 for abcdef1, abcdef12, and abcdef13 return the correct results. I tried the same 4 tests for ntlm_hybrid(loweralpha#6-6,numeric#1-3)#0-0_* and also got the correct answers.

    Also, what platform are you running on? There is a known issue that I'm working on in which hybrids of all sizes seem to fail even verifying the table on windows.

     
  • I don't have any specific hashes, because I observed the behavior in the table tester, but for example, if you test the first chain of md5_hybrid(loweralpha#6-6,numeric#1-3)#0-0_0_10000x63130363_distrrtgen[p][i]_0.rti you will see this behavior at index 2957:

    "qsdgnl557" -> md5 -> 02d8b9a11a1265ca81ddadca836654e4 -> HashToIndex(2957) -> 184000271, which is less than m_nPlainSpaceUpToX[6].

    In general, this happens when CChainWalkContext::IndexToPlain() fails to find the correct plaintext length in the first part and triggers the conditional at line 468-469 in ChainWalkContext.cpp.

    I am working mostly under Linux, I discovered the bugs when I tried to work out the exact algorithm of the reduce function (and therefore tried to use the simple/slow version of the function to understand it more easily.)

     
  • James Nobis
    James Nobis
    2011-07-13

    The original hybrids are flawed in a few ways and will be replaced entirely.

     
  • James Nobis
    James Nobis
    2011-07-13

    • status: open --> closed-wont-fix