#21 Hybrid table keyspace broken


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).


  • 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.

  • Yngve AAdlandsvik

    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

Log in to post a comment.