Date: Fri, 16 Oct 2015 14:33:44 +0300 From: Solar Designer <solar@...nwall.com> To: john-dev@...ts.openwall.com Subject: n-Viterbi Hi, n-Viterbi is an extension of the Viterbi algorithm: https://en.wikipedia.org/wiki/Viterbi_algorithm As far as I'm aware, this extension was first introduced in "Timing Analysis of Keystrokes and Timing Attacks on SSH" by Dawn Song et al: http://users.ece.cmu.edu/~dawnsong/papers/ssh-timing.pdf As I tweeted a couple of years ago: @dawnsongtweets How about finally releasing the n-Viterbi code for your "Timing Analysis of Keystrokes and Timing Attacks on SSH"? @dawnsongtweets As discussed in 2001, I am not convinced n-Viterbi gives all answers and exactly in decreasing order of probabilities @dawnsongtweets However, if n-Viterbi actually does that and isn't more complex than what the paper says, it has many other applications I did try (re)implementing n-Viterbi from the English description at the time. It'd skip some answers and the order would be suboptimal. (I guess I should have pinged Dawn Song via e-mail again, as she didn't proceed to tweet much. I think she just got on Twitter at the time.) Good news: @mitar_m has just found what looks like an implementation of n-Viterbi, here: https://github.com/edechter/PRISM/blob/master/src/c/up/viterbi.c it's the compute_n_max() function, as called from: https://github.com/edechter/PRISM/blob/master/src/c/up/mcmc_predict.c /* Compute the candidates Es for reranking by n-Viterbi */ compute_n_max(n); Other source files/functions in that directory also look relevant (at first glance; to be confirmed). Is anyone willing to give this a try, for a potential new cracking mode for JtR? Potentially, this would replace incremental or Markov modes' suboptimal ordering with the most optimal ordering that can be inferred from the available statistics (overfitting is a risk, though). My experiments in 2001 didn't result in an algorithm that would behave as well as the paper claimed it should (Viterbi finds one most probable candidate easily, but then it's tricky for the 2nd most probable and on), but maybe it was just me, and maybe the implementation above is actually it. I think this is worth a try. Unfortunately, I don't have time for it right now. Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.