Enumerating all subsequences for password recovery v0.1

I needed to write this trivial Haskell sample for a script of mine to crack one of my passwords! :) You see, I do keep some of my passwords written down on paper. But it's not any ordinary piece of paper: it's a paper full of random characters! :-D It does help a lot against nosy audience. I also keep it with me next to high value banknotes, so I would say it's well protected. I eventually memorize most passwords this way, but until then, I only keep the position of it in mind.

It's a bad habit of mine, and I haven't been doing this before. I have only recently found myself in a need for replacing a lot of my old passwords. If I could be sure in that every workstation I sit at will have md5sum installed at the very least then a single master password would suit my needs. Come to think of it, I could put my little Psion computers in order just for this very purpose! :) You have probably heard of (cryptographically secure-) hashed password generation before.

So let's get back to the main problem. I had to encrypt a file in a hurry a full month ago, so I used my "cheat sheet" again. As it was planned to be one-off use, I hardly tried to memorize the password. Sadly, I forgot to decrypt it right away, so it was lingering on my portable storage device until now. But I couldn't recall neither the position nor the length of the password precisely by then! Thankfully, I could recall the approximate place and I could narrow down a range of possible lengths. I generally use completely random passwords that are between 10 and 16 characters long. Depending on circumstances, I sometimes use a length outside this range and a narrower set of characters.

I had manually tried a dozen probable combinations at first, without success. Then I have decided to write the code below and a script to try a batch of passwords based on the output. Naturally, it worked like a charm! ;)

#!/usr/bin/runhugs
-- Calculates those subsequences of a string which
-- have a length between the specified bounds.
--
-- Copyright (c) bkil, 2009
-- License: GNU GPL v2 (or later), see the
-- attached gpl-2.0.txt for details.
--
--Changelog:
-- 2009.02.06 v0.0 first release
-- 2009.02.09 v0.1 small optimization, minor bugfix for
-- negative maxLen cases,
-- ie. exclude the empty string ("")
--
import System.Environment --getArgs
import Data.List --sort, nub

subseqs :: Int -> Int -> [a] -> [[a]]
subseqs minLen maxLen seq
| minLen > length seq || maxLen < 0 = []
subseqs _ _ [] = [[]]
subseqs minLen maxLen seq = prefix ++ rest where
prefix = [ take n seq | n <- [ minLen .. maxLen ] ]
rest = subseqs minLen maxLen (tail seq)

output :: Int -> Int -> String -> IO ()
output mn mx s = putStr . unlines . nub . sort $
subseqs mn mx s

main = do
args <- getArgs
case args of
[s] -> output 1 (length s) s
[mx,s] -> output 1 (read mx) s
[mn,mx,s] -> output (read mn) (read mx) s
otherwise -> fail "params: minLen maxLen seq"

Comments

  1. Silly me! XD

    import Data.List( inits, tails )

    subseqs minLen maxLen = filter goodSize . possible where {
    possible = concat . map tails . inits ;
    goodSize a = length a >= minLen && length a <= maxLen }

    ReplyDelete

Post a Comment

Popular posts from this blog

Tftp secret of TL-WR740N uncovered

Hidden TFTP of TP-Link routers

Haskell for embedded: C output, compilers, monads, Timber