Generating string variants constrained by Levenshtein distance

[sanchopansa]

Hello,

I'm trying to recover a password I forgot for one of my crypto wallets.

What I want to do is use a couple of "master" passwords that I know I use frequently and based on them generate a (much) larger number of candidate passwords by modifying the "master" ones in hope of finding the variant that I used for the wallet.

Essentially, I want to generate all possible strings (including special characters) which are at a given Levenshtein distance for a key. For example, given a string such as "asdf123" and a Levenshtein distance of 1, the output should be all strings which are at a Levenshtein distance of 1 from "asdf123".

Is this possible to do this with the liblevenshtein-java library?

Thank you for your time!

P. S. I saw a seemingly related question here: #5, but if I understand correctly, the provided answer is doing something very different: namely, given a dictionary (words in a document) and a query term, it finds all words in the document, which are at a given Levenshtein distance to the query term. In my case, such a "dictionary" doesn't exist (it's what I'm trying to generate)

[dylon]

You can to do this, but you'll want to customize the dictionary and transition function. I'll put together a prototype and post it shortly.

[matanox]

@dylon hope all is well!

I took the liberty renaming this issue to the more generic case. Maybe I've forgotten which existing API endpoints come to aid here, but otherwise, passwords aside, I find this may be a nice augmentation useful not only for demos but for testing and even performance testing scenarios. I find it might be a very nice addition, in case the data structures implicitly support this "reversed feature" ― and if something very mathematical can be said about how the feature would yield its outputs.

[sanchopansa]

@matanster -- thanks for renaming the question. It's much more descriptive this way!

@matanster @dylon -- so in the end, is it possible to do this string generation with the library?

[neysofu]

@sanchopansa As far as my understanding of the code goes, it would be a lot of work to do what you want. You are better off with a brute-force spell-checker, which does exactly what you're asking. Maybe this blog post can help you.

[dylon]

After more investigation, generating strings is definitely possible but will require some modification. To be honest, when I realized you want a rainbow table for password cracking, I stopped working on this.

The feature would be useful for other things, so I'll work on it eventually; I welcome pull requests. As it stands, my build scripts need to be updated for the latest version of Gradle, and Java 9 has broken Lombok and TestNG. I need to fix those issues before I can work on anything else.

[sanchopansa]

IMHO that's a ridiculous reason to stop working on a very useful feature, but it's your codebase and you're free to spend your time on it as you wish in the end. I respect that.

However, I must note that there is a plethora of tools for password cracking and whole open source distros dedicated to pentesting. With a little bit of effort and basic programming knowledge anyone could accomplish what I described above, even if not in the most optimal manner, so you are not protecting anyone by not implementing this. On the other hand, having this feature would be useful for many other applications, with the first one that springs to mind being generating DNA sequences, which are at a certain Levenshtein distance from an existing one.

In the end, technology can be used for good and evil and fundamentally there is no way to protect against the latter. Not implementing something is definitely not the solution. Luckily, many people prefer to concentrate on the positives.

[matanox]

@sanchopansa I think you've gotten things quite wrong. This is open source. Nobody here is required to develop anything for you. You are enjoying other people's efforts practically for free, and you have no moral grounds to make such comments, nor are they civil at all. That said, I too would not develop a feature meant uniquely for password cracking, if that were the case, even if your story about using it to recover your own password were taken to be true. In short, I think you owe the maintainer an apology.

[sanchopansa]

@matanster -- I think you've gotten things quite wrong. I am not expecting anyone to implement anything for me. I can do it myself when necessary :) I think I made this quite clear above by saying that the owner of the codebase is free to do with it as they choose and I respect that. It is their time after all... I also haven't followed up on this issue at all and I did resolve my problems on my own, so I am not sure how you came to the conclusion that I have any expectations from the author(s) of this library, let alone claiming that my comment is not moral or civil.

I am only pointing out the fact that not implementing something because it can be used for a bad purpose is the wrong mindset. The internet, open source software and technology in general is sadly enabling a lot of very bad things to happen. Is this a reason not to develop them? As open source contributors, we should focus on the benefits that the technology brings, not halt development because something can be used with bad intentions, especially when it clearly has good applications...

[dylon]

I have an ethical responsibility to protect my consumers to the best of my abilities. I will not willingly implement a feature for malicious reasons. It is true that this feature could be used for many things, but only password cracking was referenced in the requests.

[sanchopansa]

I appreciate your work and your efforts. I am just going to say that "password cracking" can most definitely be used for non-malicious reasons as well :)

I don't want to force my opinion on anyone though and as I said I respect your choices, so let's leave it at that.