Should we consider removing Streebog from the Linux Kernel?

Should we consider removing Streebog from the Linux Kernel?

[Theodore Ts'o]

Given the precedent that has been established for removing the SPECK
cipher from the kernel, I wonder if we should be removing Streebog on
the same basis, in light of the following work:

	https://who.paris.inria.fr/Leo.Perrin/pi.html
	https://tosc.iacr.org/index.php/ToSC/article/view/7405

Regards,

						- Ted

-----------

From the Cryptography mailing list on metzdowd.com:

From: "perrin.leo@gmail.com" <perrin.leo@gmail.com>
Subject: [Cryptography] New Results on the Russian S-box

Hello everyone,

I have recently sent an e-mail to the CFRG mailing list about my results
on the S-box shared by both of the latest Russian standards in symmetric
crypto and I have been told that it might interest the subscribers of
this mailing list.

In a paper that I am about to present at the Fast Software Encryption
conference, I describe what I claim to be the structure used by the
S-box of the hash function Streebog and the block cipher Kuznyechik.
Their authors never disclosed their design process---and in fact claimed
that it was generated randomly. I established that it is not the case.
More worryingly, the structure they used has a very strong algebraic
structure which, in my opinion, demands a renewed security analysis in
its light. Overall, I would not recommend using these algorithms until
their designers have provided satisfactory explanations about their
S-box choice.

Re: Should we consider removing Streebog from the Linux Kernel?

[Vitaly Chikunov]

Theodore,

On Mon, Mar 25, 2019 at 12:45:50AM -0400, Theodore Ts'o wrote:
> Given the precedent that has been established for removing the SPECK

As far as I know Speck is removed because:

| commit 578bdaabd015b9b164842c3e8ace9802f38e7ecc
| Author: Jason A. Donenfeld <Jason@zx2c4.com>
| Date:   Tue Aug 7 08:22:25 2018 +0200
|
|   crypto: speck - remove Speck
|
|   These are unused, undesired, and have never actually been used by
|   anybody. The original authors of this code have changed their mind about
|   its inclusion. While originally proposed for disk encryption on low-end
|   devices, the idea was discarded [1] in favor of something else before
|   that could really get going. Therefore, this patch removes Speck.
|
|   [1] https://marc.info/?l=linux-crypto-vger&m=153359499015659

None of these arguments apply to Streebog.

Thanks,


> cipher from the kernel, I wonder if we should be removing Streebog on
> the same basis, in light of the following work:
> 
> 	https://who.paris.inria.fr/Leo.Perrin/pi.html
> 	https://tosc.iacr.org/index.php/ToSC/article/view/7405
> 
> Regards,
> 
> 						- Ted
> 
> -----------
> 
> >From the Cryptography mailing list on metzdowd.com:
> 
> From: "perrin.leo@gmail.com" <perrin.leo@gmail.com>
> Subject: [Cryptography] New Results on the Russian S-box
> 
> Hello everyone,
> 
> I have recently sent an e-mail to the CFRG mailing list about my results
> on the S-box shared by both of the latest Russian standards in symmetric
> crypto and I have been told that it might interest the subscribers of
> this mailing list.
> 
> In a paper that I am about to present at the Fast Software Encryption
> conference, I describe what I claim to be the structure used by the
> S-box of the hash function Streebog and the block cipher Kuznyechik.
> Their authors never disclosed their design process---and in fact claimed
> that it was generated randomly. I established that it is not the case.
> More worryingly, the structure they used has a very strong algebraic
> structure which, in my opinion, demands a renewed security analysis in
> its light. Overall, I would not recommend using these algorithms until
> their designers have provided satisfactory explanations about their
> S-box choice.

Re: Should we consider removing Streebog from the Linux Kernel?

[Eric Biggers]

Hi Vitaly,

On Mon, Mar 25, 2019 at 09:00:41AM +0300, Vitaly Chikunov wrote:
> Theodore,
> 
> On Mon, Mar 25, 2019 at 12:45:50AM -0400, Theodore Ts'o wrote:
> > Given the precedent that has been established for removing the SPECK
> 
> As far as I know Speck is removed because:
> 
> | commit 578bdaabd015b9b164842c3e8ace9802f38e7ecc
> | Author: Jason A. Donenfeld <Jason@zx2c4.com>
> | Date:   Tue Aug 7 08:22:25 2018 +0200
> |
> |   crypto: speck - remove Speck
> |
> |   These are unused, undesired, and have never actually been used by
> |   anybody. The original authors of this code have changed their mind about
> |   its inclusion. While originally proposed for disk encryption on low-end
> |   devices, the idea was discarded [1] in favor of something else before
> |   that could really get going. Therefore, this patch removes Speck.
> |
> |   [1] https://marc.info/?l=linux-crypto-vger&m=153359499015659
> 
> None of these arguments apply to Streebog.
> 
> Thanks,
> 
> 
> > cipher from the kernel, I wonder if we should be removing Streebog on
> > the same basis, in light of the following work:
> > 
> > 	https://who.paris.inria.fr/Leo.Perrin/pi.html
> > 	https://tosc.iacr.org/index.php/ToSC/article/view/7405
> > 
> > Regards,
> > 
> > 						- Ted
> > 
> > -----------
> > 
> > >From the Cryptography mailing list on metzdowd.com:
> > 
> > From: "perrin.leo@gmail.com" <perrin.leo@gmail.com>
> > Subject: [Cryptography] New Results on the Russian S-box
> > 
> > Hello everyone,
> > 
> > I have recently sent an e-mail to the CFRG mailing list about my results
> > on the S-box shared by both of the latest Russian standards in symmetric
> > crypto and I have been told that it might interest the subscribers of
> > this mailing list.
> > 
> > In a paper that I am about to present at the Fast Software Encryption
> > conference, I describe what I claim to be the structure used by the
> > S-box of the hash function Streebog and the block cipher Kuznyechik.
> > Their authors never disclosed their design process---and in fact claimed
> > that it was generated randomly. I established that it is not the case.
> > More worryingly, the structure they used has a very strong algebraic
> > structure which, in my opinion, demands a renewed security analysis in
> > its light. Overall, I would not recommend using these algorithms until
> > their designers have provided satisfactory explanations about their
> > S-box choice.

Can you elaborate on why you want to use Streebog?  When we added Speck, we
explained in great detail why it was useful from a technical perspective (before
Adiantum was ready).  I don't see any such explanation for Streebog.

- Eric

Re: Should we consider removing Streebog from the Linux Kernel?

[Vitaly Chikunov]

Eric,

On Sun, Mar 31, 2019 at 03:43:30PM -0700, Eric Biggers wrote:
> On Mon, Mar 25, 2019 at 09:00:41AM +0300, Vitaly Chikunov wrote:
> > Theodore,
> > 
> > On Mon, Mar 25, 2019 at 12:45:50AM -0400, Theodore Ts'o wrote:
> > > Given the precedent that has been established for removing the SPECK
> > 
> > As far as I know Speck is removed because:
> > 
> > | commit 578bdaabd015b9b164842c3e8ace9802f38e7ecc
> > | Author: Jason A. Donenfeld <Jason@zx2c4.com>
> > | Date:   Tue Aug 7 08:22:25 2018 +0200
> > |
> > |   crypto: speck - remove Speck
> > |
> > |   These are unused, undesired, and have never actually been used by
> > |   anybody. The original authors of this code have changed their mind about
> > |   its inclusion. While originally proposed for disk encryption on low-end
> > |   devices, the idea was discarded [1] in favor of something else before
> > |   that could really get going. Therefore, this patch removes Speck.
> > |
> > |   [1] https://marc.info/?l=linux-crypto-vger&m=153359499015659
> > 
> > None of these arguments apply to Streebog.
> > 
> > Thanks,
> > 
> > 
> > > cipher from the kernel, I wonder if we should be removing Streebog on
> > > the same basis, in light of the following work:
> > > 
> > > 	https://who.paris.inria.fr/Leo.Perrin/pi.html
> > > 	https://tosc.iacr.org/index.php/ToSC/article/view/7405
> > > 
> > > Regards,
> > > 
> > > 						- Ted
> > > 
> > > -----------
> > > 
> > > >From the Cryptography mailing list on metzdowd.com:
> > > 
> > > From: "perrin.leo@gmail.com" <perrin.leo@gmail.com>
> > > Subject: [Cryptography] New Results on the Russian S-box
> > > 
> > > Hello everyone,
> > > 
> > > I have recently sent an e-mail to the CFRG mailing list about my results
> > > on the S-box shared by both of the latest Russian standards in symmetric
> > > crypto and I have been told that it might interest the subscribers of
> > > this mailing list.
> > > 
> > > In a paper that I am about to present at the Fast Software Encryption
> > > conference, I describe what I claim to be the structure used by the
> > > S-box of the hash function Streebog and the block cipher Kuznyechik.
> > > Their authors never disclosed their design process---and in fact claimed
> > > that it was generated randomly. I established that it is not the case.
> > > More worryingly, the structure they used has a very strong algebraic
> > > structure which, in my opinion, demands a renewed security analysis in
> > > its light. Overall, I would not recommend using these algorithms until
> > > their designers have provided satisfactory explanations about their
> > > S-box choice.
> 
> Can you elaborate on why you want to use Streebog?  When we added Speck, we
> explained in great detail why it was useful from a technical perspective (before
> Adiantum was ready).  I don't see any such explanation for Streebog.

Our users demand that file integrity is implemented using their national
standard algorithm.

Thanks,

Re: Should we consider removing Streebog from the Linux Kernel?

[Jordan Glover]

On Monday, April 1, 2019 10:04 AM, Vitaly Chikunov <vt@altlinux.org> wrote:

> >
> > Can you elaborate on why you want to use Streebog? When we added Speck, we
> > explained in great detail why it was useful from a technical perspective (before
> > Adiantum was ready). I don't see any such explanation for Streebog.
>
> Our users demand that file integrity is implemented using their national
> standard algorithm.
>
> Thanks,

Does it mean that every state can demand from Linux kernel to carrying crypto
algorithms of their choice?

Jordan

RE: Should we consider removing Streebog from the Linux Kernel?

[Pascal Van Leeuwen]

> On Monday, April 1, 2019 10:04 AM, Vitaly Chikunov <vt@altlinux.org> wrote:
>
> > >
> > > Can you elaborate on why you want to use Streebog? When we added
> > > Speck, we explained in great detail why it was useful from a
> > > technical perspective (before Adiantum was ready). I don't see any such
> explanation for Streebog.
> >
> > Our users demand that file integrity is implemented using their
> > national standard algorithm.
> >
> > Thanks,
>
> Does it mean that every state can demand from Linux kernel to carrying crypto
> algorithms of their choice?
>
I doubt that states can have that kind of leverage over the main linux kernel,
but they DO have that kind of leverage over local companies and individuals.
And it is not uncommon for states not  to trust any "western" crypto and
*mandate*(!) the use of specific home-grown algorithms instead.
So if you need to facilitate such requirements from your device incorporating
Linux, it's terribly convenient for those algorithms to be part of the mainline kernel.
As the alternative would be to either maintain those outside of the kernel tree
or to fork the kernel in its entirety, considering you *must* support them.

i.e. you can't blame them for trying ... and what WOULD be a good reason for
including a certain algorithm anyway?

Regards,
Pascal, HW Security Architect

RE: Should we consider removing Streebog from the Linux Kernel?

[Jordan Glover]

On Monday, April 1, 2019 11:44 AM, Pascal Van Leeuwen <pvanleeuwen@insidesecure.com> wrote:

> > On Monday, April 1, 2019 10:04 AM, Vitaly Chikunov vt@altlinux.org wrote:
> >
> > > > Can you elaborate on why you want to use Streebog? When we added
> > > > Speck, we explained in great detail why it was useful from a
> > > > technical perspective (before Adiantum was ready). I don't see any such
> > > > explanation for Streebog.
> > >
> > > Our users demand that file integrity is implemented using their
> > > national standard algorithm.
> > > Thanks,
> >
> > Does it mean that every state can demand from Linux kernel to carrying crypto
> > algorithms of their choice?
>
> I doubt that states can have that kind of leverage over the main linux kernel,
> but they DO have that kind of leverage over local companies and individuals.
> And it is not uncommon for states not to trust any "western" crypto and
> mandate(!) the use of specific home-grown algorithms instead.
> So if you need to facilitate such requirements from your device incorporating
> Linux, it's terribly convenient for those algorithms to be part of the mainline kernel.
> As the alternative would be to either maintain those outside of the kernel tree
> or to fork the kernel in its entirety, considering you must support them.
>

So if they have leverage over companies and individuals they have leverage over
the linux kernel too :)

I wonder what will be the limits of this leverage. Imagine some state (eastern or
western, north or south) starts to require using backdoored crypto because they
don't trust something they can't break. Will linux kernel comply?

> i.e. you can't blame them for trying ... and what WOULD be a good reason for
> including a certain algorithm anyway?
>

Technical soundness and problems it solves. Speck was already given as example.
It was needed due to performance constraints on lower-end devices and when it
wasn't needed anymore it was thrown to the bin.

> Regards,
> Pascal, HW Security Architect

Jordan