It has been well understood for decades that exhaustive search through 2^k keys costs considerably fewer operations than 2^k separate cipher evaluations. Neither 2011/417 nor 2012/617 deserve any credit for this.
Here are a few examples from the literature---certainly not the first examples; it's hard to trace the history of such an obvious idea.
]: "The attacker is trying to find a 16-byte AES key k, given the 16 bytes H(k) = AES_k(8675309). There's nothing special about the number 8675309, or about AES: this is a brute-force attack that applies to a huge variety of ciphers. ... Distribute H(k_1) to many circuits, each of which searches sequentially through a range of possibilities for k_1. Computations for one key can be merged to some extent with computations for the next key, saving time."
]: "The Salsa20 security conjecture is that one cannot simultaneously achieve a substantially better price, performance, and chance of success ... The word 'substantially' makes room for minor speedups. For example, the following tradeoff often improves price-performance ratio: a key-search unit can perform a partial hash-function evaluation, saving time at the beginning and end of the computation, by taking advantage of the fact that a single-bit key change does not instantaneously affect all 512 bits inside Salsa20."
]: "Reduce the DES encryption from 16 rounds to the equivalent of ~9.5 rounds, by shortcircuit evaluation and early aborts."
Of course, for ciphers with short keys there's considerable value to the attacker in really optimizing this type of speedup (as illustrated by the 9.5 above). The exact attack costs are of course highly dependent upon the cipher details. But this dependence is at a ludicrously small scale compared to the dependence upon the key length.
Describing a change from 2^56 to 2^55 or 2^54 as a "weakness" in a cipher is completely missing the big picture that _every_ 56-bit cipher is weak. Trying to maximize the strength of a 56-bit cipher (hey, let's repeat DES 1000 times, hoping that the attack becomes 1000 times slower!) is a pointless exercise; users should simply move to larger keys.
A change from 2^128 to 2^127 or 2^126 is obviously of even less importance. A change from 2^256 to 2^255 or 2^254 is of no importance at all.
---D. J. Bernstein
University of Illinois at Chicago; Technische Universiteit Eindhoven