Re: Interleaved CBC

[Andy Polyakov]

> Basically, I'm wondering if interleaved CBC or some other parallelized
> cipher method is available in OpenSSL.

No.

> If its not available I was
> wondering if there were any specific reasons that made it impossible, or
> highly difficult, to actually implement.

Well, a library such as OpenSSL is not really a place to implement such
things. For several reasons. "Philosophical" such as who is taking care
of signals [trouble is that signals can be delivered to any thread and
how would library now which handlers to install, it's application
business, not library such as OpenSSL] and practical such as performance
impact [does one start and terminate thread for every block? what impact
on performance does syncronisation have on every platform?]. In other
words you should look at OpenSSL as multi-thread safe primitive provider
and take care of parallelization in application.

> For background - I've found that on the multicore and SMP machines we
> have OpenSSL encryption usually ends up pegging one core but leaving the
> rest of the machine idle. I was hoping to improve overall encryption
> performance by making better use of the CPU resources available to me.

Keep in mind that message authentication is approximately as CPU
consuming as encryption. In other words one can as well consider
pipe-lining these two operations. I mean having two packets to work on
at every time you can calculate MAC for one packet and encrypt previous
(or vice versa in decrypt case). A.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List opens...@openssl.org
Automated List Manager majo...@openssl.org

[Chris Rapier]

Thanks for taking the time to reply.

Andy Polyakov wrote:
>> Basically, I'm wondering if interleaved CBC or some other parallelized
>> cipher method is available in OpenSSL.
>
> No.

Okay, this is what I thought but I wanted to make sure.

>> If its not available I was wondering if there were any specific
>> reasons that made it impossible, or highly difficult, to actually
>> implement.
>
> Well, a library such as OpenSSL is not really a place to implement such
> things. For several reasons. "Philosophical" such as who is taking care
> of signals [trouble is that signals can be delivered to any thread and
> how would library now which handlers to install, it's application
> business, not library such as OpenSSL] and practical such as performance
> impact [does one start and terminate thread for every block? what impact
> on performance does syncronisation have on every platform?]. In other
> words you should look at OpenSSL as multi-thread safe primitive provider
> and take care of parallelization in application.

A bit of background - I've done some work in optimizing OpenSSH in the
past by working on buffer constraints
(http://www.psc.edu/networking/projects/hpn-ssh). We've pretty much
reached the limit of what we can do vis a vis flow control and wanted to
look at new ways of increasing performance. Since we expect the majority
of our file transfer node to be multicore we thought parallelizing SSH
might be a good place to start.

We've done some preliminary work with parallelizing the CTR mode of AES
(whats nice is the the resultant data stream is indistinguishable from a
single non-parallelized stream) with encouraging results. We wanted to
look at CBC mode (based on the paper Accelerating Private-Key
Cryptography via Multithreading on Symmetric Multiprocessors [Dongara,
Vijaykumar www.ece.purdue.edu/~vijay/papers/2003/icbc.pdf]) to see how
it compared.

Before we devoted anymore time to it I wanted to check to see if it had
been tried and then abandoned for some technical reason we had
overlooked. If anyone is interested in our results I can post them here.

>> For background - I've found that on the multicore and SMP machines we
>> have OpenSSL encryption usually ends up pegging one core but leaving
>> the rest of the machine idle. I was hoping to improve overall
>> encryption performance by making better use of the CPU resources
>> available to me.
>
> Keep in mind that message authentication is approximately as CPU
> consuming as encryption. In other words one can as well consider
> pipe-lining these two operations. I mean having two packets to work on
> at every time you can calculate MAC for one packet and encrypt previous
> (or vice versa in decrypt case). A.

We've actually been looking at implementing something similar to this.

Thanks very much for your time, I do appreciate it.

Chris Rapier
Pittsburgh Supercomputing Center

[Andy Polyakov]

>>> Basically, I'm wondering if interleaved CBC or some other
>>> parallelized cipher method is available in OpenSSL.
>>

>> No. ... you should look at OpenSSL as multi-thread

>> safe primitive provider and take care of parallelization in application.

If there is remote possibility that interleaved CBC can be adopted as
approved mode of operation or if there is consensus that it does not
impose extra security risk, then one can discuss implementing an ICBC
*primitive* in OpenSSL. But I'd still expect application to take care of
threading.

> Before we devoted anymore time to it I wanted to check to see if it had
> been tried and then abandoned for some technical reason we had
> overlooked. If anyone is interested in our results I can post them here.

If nobody else expresses interest, feel free to send it to me.

>>> For background - I've found that on the multicore and SMP machines we
>>> have OpenSSL encryption usually ends up pegging one core but leaving
>>> the rest of the machine idle. I was hoping to improve overall
>>> encryption performance by making better use of the CPU resources
>>> available to me.
>>
>> Keep in mind that message authentication is approximately as CPU
>> consuming as encryption. In other words one can as well consider
>> pipe-lining these two operations. I mean having two packets to work on
>> at every time you can calculate MAC for one packet and encrypt
>> previous (or vice versa in decrypt case).
>

> We've actually been looking at implementing something similar to this.

I personally would even argue that this should be done first. Point is
that if hash procedure and cipher are in perfect balance (i.e. have same
performance), then parallelizing cipher won't give you overall ~2x
improvement, while pipe-lining would. Cipher has to be a lot slower than
hash in order to provide more overall gain as result of its
parallelization than from pipe-lining. And vice versa, if hash is a lot
slower than cipher then it makes lesser and lesser sense to parallelize
cipher. A.