Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Typically,I think latency should mean the time from the first plaintext input to the first ciphertext output, when the block cipher is not totally unrolled (such as AES unrolled with 2 rounds).

If I use a pipeline to increase the throughput, the latency should relate to the amount of pipelined data. E.g. with AES unrolled with 2 rounds, and 100 group data to create the pipeline, then the latency must be larger than 500 cycles (except the time to calculate).

But in many papers, latency in this situation does not include this number, just the clock cycles of 10 rounds' critical path.

I do not understand why.

Also, what is the requirement of latency which limits the number of blocks which are pipelined?

share|improve this question
add comment

migrated from security.stackexchange.com Aug 24 '13 at 21:45

This question came from our site for Information security professionals.

1 Answer

When talking about a circuit (FPGA, ASIC...) implementing some encryption algorithm, the relevant measures are:

  • Bandwidth: how many input bytes can be processed per second.
  • Latency: how much time occurs between the moment an input byte (or block) is injected, and the corresponding output byte (or block) is obtained.
  • Circuit area, energy consumption...

AES (with 128-bit keys) is defined as using 10 successive rounds; the important point being that each round works over the output of the previous round. Thus, the ten rounds MUST be computed sequentially. However you implement it, the data block will have to go ten times through a circuit computing one round. Ten times through the same circuit, or five times through two copies of the circuit, or through ten distinct copies of the circuit: this does not matter here. The latency for an AES invocation is related to the number of rounds.

If you do a loop, with a single circuit for one round and some gates to reuse that circuit ten times, then you will have minimal total circuit area, but also lowest bandwidth, because you will have to wait for completion of the ten rounds before starting a new AES invocation. For instance, if processing one round takes one clock cycle, then you will have a latency of 10 cycles (it takes 10 cycles to get an encrypted block from the plaintext block), and a bandwidth of one block per 10 cycles. If you "unroll" the implementation with 10 copies of the "round" circuit, then latency will still be 10 cycles: when you inject one block, the corresponding output block will be available 10 cycles later. However, you can then inject one block per cycle: ten times the circuit area, but also ten times the bandwidth.

To sum up, loop unrolling and pipelining in a circuit does not change the latency, but the bandwidth.


All of the above is about doing "AES invocations", i.e. applying the AES algorithm on 16-byte blocks which are independent of each other. When encrypting a message (as a potentially very long sequence of bytes), you are using the AES through a block cipher mode of operation which can add its own constraints. For instance, if using CBC, then, by construction, you need the result of the encryption of one block before beginning the encryption of the next block (because you first XOR each block with the previous encrypted block). Therefore, even if you have a fully unrolled AES circuit with a latency of 10 cycles and a bandwidth of one block per cycle, you will not be able to encrypt more than one block every 10 cycles. Conversely, CTR mode allows for the full bandwidth of one block per cycle, because all the elementary encryptions in CTR can be done in parallel.

Here, I am not talking about the latency of the block cipher itself (AES), but the latency induced by its mode of operation.

If we go one step further and think about overall message processing: consider SSL/TLS. In SSL, data is encrypted as records where each record contains up to 16 kB of data, and has its own MAC. Upon receiving a record, an SSL implementation must first verify the MAC over the complete (decrypted) record before beginning to use the data (until the MAC is verified, the SSL implementation cannot assume that the data has not been altered). This means a much higher latency: between the time the first encrypted record byte is received and the time the corresponding plaintext byte is really available, the decryption and MAC processing of the whole record must occur.

This example shows that the notion of "latency" is flexible and occurs at many levels, so it is important to be clear about what we are talking. In the case of a block cipher like AES, the "latency" is about the minimum processing time for one block independently of other blocks. This translates to the latency for a "message" only insofar as the encryption mode and other protocol characteristics like a MAC do not add their own constraints.

share|improve this answer
    
Thank you very much for your answer , but i still have some doubts. That is, of caouse ,when all the round is unrolled ,the latency is the critical path length.But, in ECB or CTR, when the loop is partical unrolled, such as 2 rounds,we should reuse the circults for 5 times, in this situation ,if we assume that it takes 4 clock cycles to finish one round,then it takes 8 cycles to finish 2 rounds,and the latency is 4x10=40 cycles. –  Bo Wang Aug 25 '13 at 2:40
    
But,to improve the throughput in ECB or CTR,we should use pipline,for example, use 100 group plaintexts to creat pipline,then the time is (4x2+100-1)x5=535,and 535/100=5.35 for 1 group ,then the throughput is 128bit/5.35cycle = 23.9 bit per cycle. It is larger than 128/(4x10)=3.2 bit per cycle. But the improve of throughput makes the time of the output of the first group much slower ,which is 535 cycles,larger than 40 cycles. And if we assume the number 100 is changed to infinity,then the throughput is 128/5=25.6 bit per cycle,which is the largest in this partical unrolled situation. –  Bo Wang Aug 25 '13 at 3:01
    
But the latency is infinity,too.So in order to deside the number of groups which creat the pipline,we should tradeoff between latency and throughput.But,in some good papers,their result of the partical unrolled situation is the best throughput (such as 25.6 bit per cycle with infinity groups) with the lowest latency(such as 40 cycles).I think it is not fair. We should reflect the latency cost with the throughput ,such as 23.9 bit per cycle with latency of 535-99=436 cycles. –  Bo Wang Aug 25 '13 at 3:18
    
(there is an error earlier which is that the latency shouled be 436 instead of 535 because in the 436 cycle the first group output already ). –  Bo Wang Aug 25 '13 at 3:19
    
I think about it again,the latency is neither 535 cycles nor 436 cycles. It should be (4x2+100-1)x4 + 4 +1(for output)=433 cycles –  Bo Wang Aug 25 '13 at 4:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.