technology from back to front

Archive for February, 2014

Predicting and controlling correlations in differentials of addition mod 2^{n}

This is a paper I wrote in collaboration with Scott Fluhrer in 2005. It was not accepted for FSE 2006; it would have been better if I hadn’t waited until 2014 to make it public, but better late than never.

It arose from a discovery I made when developing attacks on Salsa20 for “Truncated differential cryptanalysis of five rounds of Salsa20”. Several of the attacks were twice as effective as my calculations showed they should have been. I remarked in the paper “By experiment, we have even determined a few differential trails whose probability appears to be twice as high as their weight would suggest—this is presumably because of problems with the independence assumption”. Digging deeper, I discovered why these trails did not behave independently, and developed an algorithm for correctly predicting the probability that the trail holds; this algorithm works across a wide range of “ARX” (addition, rotation, XOR) cryptographic primitives. The obvious person to talk to about these ideas was Cisco’s Scott Fluhrer, whose expertise in differential cryptanalysis led to him breaking the cipher in my first publication, Mercy. Scott pointed me to the ARX MAC “Michael”, and we found that the same technique could be used to analyse an anomaly in Michael.

In all likelihood this is just a historical curiosity; the right place to look now would be the ARX toolkit and associated papers.

Paul Crowley, Scott Fluhrer, Predicting and controlling correlations in differentials of addition mod 2^{n} (PDF).

Paul Crowley

A study in Scala

Cards on the table: I like Scala. Right now it’s my go-to general purpose programming language, but I know that many people have a dim opinion of it, or appreciate its positives but are heavily conflicted by its negatives. Actually I do put myself in that latter camp, though I think I’ve got deep enough into learning the language that I can get past most of those negatives. Here I present a classic tale of “life with Scala”.

The problem

Scala generally has collection methods for most things you can think of, so I was pleased but not surprised to find inits and tails methods, that list all of the prefixes and suffixes respectively. These methods return an iterator, hence the use of toList below, to actually see the results. For the rest of this post, we’ll just consider inits, though tails is trivially similar.

scala> List(1,2,3).inits
res1: Iterator[List[Int]] = non-empty iterator

scala> List(1,2,3).inits.toList
res2: List[List[Int]] = List(List(1, 2, 3), List(1, 2), List(1), List())

scala> List(1,2,3).tails.toList
res3: List[List[Int]] = List(List(1, 2, 3), List(2, 3), List(3), List())

The results include the empty collection, but as it happens that doesn’t suit my needs. I want a version that doesn’t return the empty list.

What to do?

Options include:

  • Call the existing inits method then strip off the last item. However since we get an iterator this isn’t quite so trivial – we can’t just do inits.init
  • Write a new custom method to do just what I want and return a collection, not an iterator.

I decided, in the spirit of Scala, that I would add a nonEmptyInits method to ‘all collections’ (and I’m deliberately vague here) via an implicit conversion, so that it can be called just as easily as inits. It would call inits but wrap the iterator to exclude the final element. Easy peasy, but the rabbit hole loomed ahead of me.

Because I was over-engineering and trying to be purist (this was hobby code) I wanted to implement my new method for the most generic type reasonable. Figuring out what type that was challenged me rather. The Scala collections API has a fairly complicated hierarchy. This is somewhat diagrammed and explained in the documentation but that doesn’t show all the interim traits and classes that are in the guts of the implementation such as TraversableLike, GenTraversable, GenTraversableLike and 10+ others relating just to Traversable. The API is setup to support some very clever facilities, like generic collection methods typically returning collections of the same type you started with. Apparently most libraries can’t/don’t do this. However it made it hard for me to find the right place to start. Ultimately I settled on Traversable, since inits itself is defined in TraversableLike, but adding to that directly seemed like more trouble than it was worth.

implicit class TraversableExtras[T](t: Traversable[T]) {
  def nonEmptyTails: Iterator[Traversable[T]] = {
    val bufferedInits = t.inits.buffered
    new Iterator[Traversable[T]] {
      def hasNext() = bufferedInits.head.nonEmpty
      def next() =

My solution above wraps the iterator with a buffered version, so that I can peek at head and determine whether to end early or not. This is fairly nice and simple and I’m quite happy with it. It means we can do the following, via the magic of implicit conversions.

scala> List(1,2,3,4).nonEmptyTails.toList
res7: List[Traversable[Int]] = List(List(1, 2, 3, 4), List(1, 2, 3), List(1, 2), List(1))

But Arrays mess it all up

This is all looking very promising and straightforward, but it took a fair bit of banging my head against the desk to figure out why the compiler wouldn’t let me call it on an Array.

scala> Array(1,2,3).nonEmptyTails
:9: error: value nonEmptyTails is not a member of Array[Int]

To cut a long story short, though we can seamlessly treat Array as a Traversable, Array is actually somewhat special. It maps to Java arrays for implementation reasons, but supporting generics, and with an implicit conversion to WrappedArray, which is a Seq (and hence a Traversable) to provide all the collection methods we’re used to. So far so good, but it turns out that the compiler cannot apply more than one implicit conversion at a time, as the search space would explode. Hence it cannot convert from Array to WrappedArray to my TraversableExtras. A solution in such a case, where we want two conversions, is to explicitly cast the Array, to make the first conversion explicit, then the compiler does the rest.

scala> (Array(1,2,3): Traversable[Int]).nonEmptyTails
res10: Iterator[Traversable[Int]] = non-empty iterator


Finally I got where I wanted, even if that cast is a bit irritating, and I learned a lot of useful things in the process – all part of the journey of familiarity with any language. But it struck me as soon as I got a bit lost in the Scala collections hierarchy that I was on a mission with which I am all too familiar. It was at that point that I decided I would probably blog about the experience and started taking notes!

I still like Scala, but I’m very well aware that this is the price I pay, and I’m not surprised that others find it too high a price.

Just to be clear…

I realise by the way that this was all a fools errand in the first place. I deliberately went down the path described above as an explicit learning exercise because I wanted to get more experience with the collections API, iterables, implicits etc. It is possible to achieve the result more directly with a filter:

scala> Array(1,2,3).inits.filter(_.nonEmpty).toList
res16: List[Array[Int]] = List(Array(1, 2, 3), Array(1, 2), Array(1))

It’s not quite as pithy as having a nonEmptyTails method, but in all other senses it’s probably superior.

Sam Carr

Facebook android security fail

I wrote about the Ocado android applications ridiculous privileges ¬†list a while back. Facebook has reminded me of it:¬†Facebook app now reads your smartphone’s text messages? THE TRUTH.

Facebook want to be able to capture the two factor auth message straight from your text messages, so they ask for access to all your text messages.

What should happen, is that there’s a two factor auth agent app, which has access to your text messages. Other apps register with it – specifying that they wish to receive text messages from a particular sender. When they do this, the agent asks the user if that’s allowed. That’s better, because the agent is a small and simple app, and if lots of apps share it, we can spend more on it, further cutting down on faults.

Because this app doesn’t exist yet, someone trusted needs to write it. Facebook could write it but why would they do that? most users user’s wouldn’t understand the difference. Lot’s of people argue that the someone trusted should be Google, and the agent should be part of Android.

I think this is a great opportunity for a security brand to build it’s reputation: it can create a suite of applications like this, and then offer to endorse apps which use them, and follow a set of guidelines.

This could be implemented with something as simple as a trademark on the apps page, but it’s preferable that endorsements are cryptographically signed certificates, and android displays endorsements before installation. App developers would pay for the endorsement – either by paying for the review, or by a share of revenue.

This is a much more positive role for a security brand than offering virus checking, since it will significantly reduce zero day exploits, by increasing software quality. It’s also the only way open, since Google aren’t allowing third parties to block app installation. Building a brand seems to be something the industry knows how to do, we should harness that to improve software quality.

I need to add a couple of things to this. One is an oversight, and the other came to my attention just after writing the above:

The Google+ app recently asked to read your text messages – it incorporates them into the user interface. I don’t know if Google are slurping text messages as a result, but the security implications are exactly the same.

Facebook have released a library designed to help app developers safeguard users data on Android devices using cryptography. I haven’t looked at it to asses it’s efficacy, but as I’ve noted here before, Android doesn’t provide access to the phones hardware key storage mechanisms on any phone I’m aware of, so it’s not obviously possible for this library to be effective.





You are currently browsing the LShift Ltd. blog archives for February, 2014.



2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us