If $F:\{0,1\}^k \times \{0,1\}^{m} \rightarrow \{0,1\}^{n}$ is a PRF, then define $$G:\{0,1\}^{k+l} \times \{0,1\}^{m} \rightarrow \{0,1\}^{n+l}$$ as $$G(s.s';x)=F(s;x).s'$$(here . means concatenation) where, $x \in \{0,1\}^m, s \in \{0,1\}^k, s' \in \{0,1\}^l$, how to show that $G$ is indeed...
@ThomasPornin I think so - it's mathematics heavy but essentially covers most of elliptic curves, which is exactly what I was after. It starts with finite fields, then arithmetic on elliptic curves and goes from there.
It does cover implementation points too, which I also liked.
I have been searching for a few days now, but I cannot find a big-O notation algorithm for encrypting, decrypting, or attempting to break an encrypted file (brute force) making use of public key encryption. I am attempting to determine the big-O notation of an idea I have developed that makes hea...
@ThomasPornin From the look-inside thing it looks very similar in terms of contents; the one I have is 100 pages shorter, though and doesn't present a list of algorithms. I don't own it; but I'd be interested in the comparison also.
The LMS lecture note series are very much lecture-notes like, rather than necessarily as verbose as a book, kinda like Springer graduate texts. Sometimes, I find they're just what I need and sometimes I wish I'd brought something more meaty.
@ThomasPornin Both of them are in our library, I'll take a look in the next days. (The one by Blake is still gone until Thursday, I've reserved it now).
That one seems to be "the sequel". It is a bit lacking in homogeneity (it is basically an assembly of independently written chapters by distinct people).
Rijndael's S-box is a frequently used operation in AES encryption and decryption. It is typically implemented as a 256-byte lookup table. That's fast, but means you need to enumerate a 256-byte lookup table in your code. I bet someone in this crowd could do it with less code, given the underly...
There are assertions in the comments that the S-box would fit into the cache together with the code ... is this the case for modern processors? (I have about no knowledge about computer hardware.)
@PaŭloEbermann In most modern processors, data and code live in separate caches
Also, the problem is not about size
rather, it goes like this: in a modern cache, a given memory location can be cached only in a few specific cache location
e.g. bye at address x can go to only 2 or 4 places in the cache
it is then conceivable to "knock out" of the cache some specific table entries by having some code which (concurrently or just before) performs memory accesses which result in using the same cache locations
then AES invocation would be slowed (a cache miss can use hundreds of clock cycles) if and only if it hits these same table entries, which depends on the key
This assumes that you can make the target system process some data in a semi-controllable way, and that you have accurate timing information.
In a lab, you can arrange for the "process external data" to be handling of an incoming UDP packet, and with enough AES decryptions you can get the timing information with some heavy statistics. But you need some very precise knowledge of the target code, you must be on the same link to get enough timing accuracy, and it takes all day.
I remember having read (or skimmed over) a paper about one such attack ... where the attacker actually sat on the same computer, and did not have access to the data, only measured its own data access times (i.e. cache misses).
@PaŭloEbermann Must have been Thomas. I'm convinced all cryptographers must really be Thomas! On a serious note, "In most modern processors, data and code live in separate caches" is the hybrid von neumann vs harvard architecture design. Essentially:
harvard architecture = data and code separate (good luck doing dynamic languages, but awesome for security - good luck injecting code!)
von neumann = mixed code and memory. Modern processors are mixed for this reason (separate caches, but one main memory) if I understand it right.
When some bytes come to the cache, we usually already know if we want to interpret them as data or code, while this might not yet true in the main memory.
So, is my requirement sensible or not?
> Bonus points (upvotes from me) if the resulting function is constant-time (i.e. no data-dependent code paths or array accesses or whatever your language supports)
@PaŭloEbermann data dependent code paths = branching, which has a cpu cost. If you want efficient code, you often do things like loop unrolling, because as I understand it instruction prefetching prefers sequential code - secure.wikimedia.org/wikipedia/en/wiki/Instruction_prefetch
@PaŭloEbermann I know, but depending on what the branch prediction code does, you will get different timings depending on different outcomes. In terms of optimisation you only care that it costs more, but in terms of timing attacks those times might be significant, I don't know.
It sounds from what Thomas said that such an attack would require lab conditions to pull off, if the effect of branching actually produces significant data.
@Ninefingers There have been lab-demonstrated attacks using table accesses (with cache effects) and branch prediction (modern CPU try to predict whether a given conditional jump opcode will be taken or not; they do so with some ad hoc rules, and an internal specific cache).
A constant-time implementation is a "selling point", at least academically
thus, what @Paŭlo requests is relevant
on a more general basis, a constant-time implementation is also, with high probability, an implementation which would map well to a FPGA/ASIC circuit
@ThomasPornin aaahhh ok. I wasn't sure whether the branch prediction and the associated cost whilst it does this (and when it has to refresh the cached code) was actually statistically enough evidence to attack a cipher with.
@Ninefingers It has been argued that the branchless, table-less block cipher Serpent is completely immune to such attacks, and that it should have been chosen as AES instead of Rijndael.
So I've often looked at serpent and thought it was a very strong contender in AES. Not so long ago I was looking for evidence as to why it didn't beat rijndael. So far, the closest I've got answering that is this:
The 32 rounds means that Serpent has a higher security margin than Rijndael; ho...
In which case , does repeated encodings gives back the plain text ?
any idea ?
Rijndael's S-box is a frequently used operation in AES encryption and decryption. It is typically implemented as a 256-byte lookup table. That's fast, but means you need to enumerate a 256-byte lookup table in your code. I bet someone in this crowd could do it with less code, given the underly...
So I've often looked at serpent and thought it was a very strong contender in AES. Not so long ago I was looking for evidence as to why it didn't beat rijndael. So far, the closest I've got answering that is this:
The 32 rounds means that Serpent has a higher security margin than Rijndael; ho...
