Implemented an "unmunger"

[Ronan-H]

For issue #45

Arbitrary string to string substitution implemented, so "P@55uu0rd" -> "password" works, as does "8u2T3RfL?" -> "butterfly" from the wikipedia page. I wrote DictionaryMatcher.testArbitraryLengthSubstitutions() to test a few more examples. leetTable has been replaced by the MungeTable class which facilitates some of the substituting. MungeTable is initialized in ConfigurationBuilder as before, you can try adding some more substitutions there, I just added the few from the wikipedia page and some extra ones that I thought up. PasswordChain is used to store the list of possible substring permutations. I rewrote translateLeet as getUnmungedVariations, and rewrote replaceAtIndex. They kind of work in the same way, just with a list of String[] instead of an in-place char array. There are some very obscure limitations, but I doubt they could be much of an issue. Efficiency wise it's probably worse than before, but I guess it depends on what your expectations are. It still takes a fraction of a second to estimate a reasonably sized password, at least.

Also, I changed the pom.xml java version from 1.7 to 8 so I could use streams and lambdas, is that an issue?

Let me know if you want me to do more on this, I'm sure it's not perfect. There are loads of occurrences of "leet" in comments and method names etc. that should probably be something like "munge" now...

[Ronan-H]

Some of the limitations I was thinking of are:

1. Longer munges are checked before shorter ones, so in the case of 2n -> nn, the possibility of 2 -> z won't be checked (I think, I tried to test this but I was very confused by the results). This could be worked around by simply adding zn as a possible unmunge of 2n directly.

2. In the case of a string like "uuu", "wu" would be generated as a permutation but "uw" would not. This is because once a replacement is made, the replacement is never undone in search of other rearrangements like that. Fixing this would maybe involve using a tree type structure to exhaust every combination like that as well.

3. Cases like someone using multiple replacements 2n -> nn -> m aren't handled directly, as with the first limitation they can just be added directly to the MungeTable so 2n -> m is a possibility.

4. Reversed munged passwords can't be unmunged, unless they're symmetrical, I would imagine. This is probably good for the most part: |) should become D, but )| no longer resembles a D. uu -> w meanwhile should obviously work backwards.

The way you run the unmunger on every possible substring of a password might be counteracting some of these limitations, I'm not sure. Either way, those ones I listed shouldn't really be much of a concern as long as the entries in the MungeTable don't interfere with eachother.

[Tostino]

Also, I changed the pom.xml java version from 1.7 to 8 so I could use streams and lambdas, is that an issue?

Just recalled reading this. The one reason I was wanting to keep jdk 1.7 support was to allow Android developers to use the library on older SDKs, however that is probably less of a problem at this point since many more devices support SDK that has some JDK8 language support now. I'll just want to do some more research first prior to deciding to go JDK8+ for the library.

[ManfredSchenkIOSB]

any updates on his PR?

[Tostino]

Needs to have conflicts resolved. Please rebase against the "dev" branch.

If we can do some performance testing to ensure the worst-case scenario doesn't cause issues, we should do that while implementing new algorithms. The findings in: #60 were enlightening as to potential issues to look out for in the future.

[Ronan-H]

OK, so TODO:

• Rebase and resolve conflicts
• Do some overall big O performance calculations
• Come up with some worst-case passwords against this new alg and compare timings against the dev branch

I don't see any automated performance tests but that might be valuable as a separate issue to get a feel of the performance impact straight away per PR, and measure performance over time on master etc.

Should I close this and open a PR against dev instead?

[Tostino]

Yes if you don't mind making a new PR against dev, that'd be great. And yes that TODO list looks correct.

You are also right that we don't have any performance tests at this point, that is in the pipeline once I get through this bit of terribleness. I also plan on implementing: #83 to "solve" complexity explosion issues, making the need for automated performance testing less critical right away.

[Ronan-H]

New PR to be opened against dev...