@SteveBellovin@infosec.exchange @cryptomancer The short answer: They improve an attack from 2013 (Derbez et al.), based on our improvement from 2010, of an attack by Demirci and Selcuk. They save a byte guessing in a very innovative way, but I am not sure that the true gain is x200 to x800 (or more precisely, I am sure that the ALGORITHMIC gain is not that big, but as they can access smaller tables, then it may be faster in real life).