[<prev] [next>] [day] [month] [year] [list]
Message-ID: <20151016113344.GA19196@openwall.com>
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.
