Solar Designer

2015-10-16 11:33:44 UTC

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

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