Re: better patch for linux/bitops.h
On 05/05/2016 03:18 PM, ty...@mit.edu wrote: > > So this is why I tend to take a much more pragmatic viewpoint on > things. Sure, it makes sense to pay attention to what the C standard > writers are trying to do to us; but if we need to suppress certain > optimizations to write sane kernel code --- I'm ok with that. And > this is why using a trust-but-verify on a specific set of compilers > and ranges of compiler versions is a really good idea > For the record, the "portable" construct has apparently only been supported since gcc 4.6.3. -hpa -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On May 5, 2016 3:18:09 PM PDT, ty...@mit.edu wrote: >On Thu, May 05, 2016 at 05:34:50PM -0400, Sandy Harris wrote: >> >> I completely fail to see why tests or compiler versions should be >> part of the discussion. The C standard says the behaviour in >> certain cases is undefined, so a standard-compliant compiler >> can generate more-or-less any code there. >> > >> As long as any of portability, reliability or security are among our >> goals, any code that can give undefined behaviour should be >> considered problematic. > >Because compilers have been known not necessarily to obey the specs, >and/or interpret the specs in way that not everyone agrees with. It's >also the case that we are *already* disabling certain C optimizations >which are technically allowed by the spec, but which kernel >programmers consider insane (e.g., strict aliasing). > >And of course, memzero_explicit() which crypto people understand is >necessary, is something that technically compilers are allowed to >optimize according to the spec. So trying to write secure kernel code >which will work on arbitrary compilers may well be impossible. > >And which is also why people have said (mostly in jest), "A >sufficiently advanced compiler is indistinguishable from an >adversary." (I assume people will agree that optimizing away a memset >needed to clear secrets from memory would be considered adversarial, >at the very least!) > >So this is why I tend to take a much more pragmatic viewpoint on >things. Sure, it makes sense to pay attention to what the C standard >writers are trying to do to us; but if we need to suppress certain >optimizations to write sane kernel code --- I'm ok with that. And >this is why using a trust-but-verify on a specific set of compilers >and ranges of compiler versions is a really good idea > >- Ted I have filed a gcc bug to have the preexisting rotate idiom officially documented as a GNU C extension. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70967 -- Sent from my Android device with K-9 Mail. Please excuse brevity and formatting. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On 05/05/2016 03:18 PM, ty...@mit.edu wrote: > On Thu, May 05, 2016 at 05:34:50PM -0400, Sandy Harris wrote: >> >> I completely fail to see why tests or compiler versions should be >> part of the discussion. The C standard says the behaviour in >> certain cases is undefined, so a standard-compliant compiler >> can generate more-or-less any code there. >> > >> As long as any of portability, reliability or security are among our >> goals, any code that can give undefined behaviour should be >> considered problematic. > > Because compilers have been known not necessarily to obey the specs, > and/or interpret the specs in way that not everyone agrees with. It's > also the case that we are *already* disabling certain C optimizations > which are technically allowed by the spec, but which kernel > programmers consider insane (e.g., strict aliasing). > > And of course, memzero_explicit() which crypto people understand is > necessary, is something that technically compilers are allowed to > optimize according to the spec. So trying to write secure kernel code > which will work on arbitrary compilers may well be impossible. > > And which is also why people have said (mostly in jest), "A > sufficiently advanced compiler is indistinguishable from an > adversary." (I assume people will agree that optimizing away a memset > needed to clear secrets from memory would be considered adversarial, > at the very least!) > > So this is why I tend to take a much more pragmatic viewpoint on > things. Sure, it makes sense to pay attention to what the C standard > writers are trying to do to us; but if we need to suppress certain > optimizations to write sane kernel code --- I'm ok with that. And > this is why using a trust-but-verify on a specific set of compilers > and ranges of compiler versions is a really good idea > In theory, theory and practice should agree, but in practice, practice is what counts. I fully agree we should get rid of UD behavior where doing so is practical, but not at the cost of breaking real-life compilers, expecially not gcc, and to a lesser but still very real extent icc and clang. I would also agree that we should push the gcc developers to add to the manual C-standard-UD behavior which are well-defined under the gnu89/gnu99/gnu11 C dialects. -hpa -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On Thu, May 05, 2016 at 05:34:50PM -0400, Sandy Harris wrote: > > I completely fail to see why tests or compiler versions should be > part of the discussion. The C standard says the behaviour in > certain cases is undefined, so a standard-compliant compiler > can generate more-or-less any code there. > > As long as any of portability, reliability or security are among our > goals, any code that can give undefined behaviour should be > considered problematic. Because compilers have been known not necessarily to obey the specs, and/or interpret the specs in way that not everyone agrees with. It's also the case that we are *already* disabling certain C optimizations which are technically allowed by the spec, but which kernel programmers consider insane (e.g., strict aliasing). And of course, memzero_explicit() which crypto people understand is necessary, is something that technically compilers are allowed to optimize according to the spec. So trying to write secure kernel code which will work on arbitrary compilers may well be impossible. And which is also why people have said (mostly in jest), "A sufficiently advanced compiler is indistinguishable from an adversary." (I assume people will agree that optimizing away a memset needed to clear secrets from memory would be considered adversarial, at the very least!) So this is why I tend to take a much more pragmatic viewpoint on things. Sure, it makes sense to pay attention to what the C standard writers are trying to do to us; but if we need to suppress certain optimizations to write sane kernel code --- I'm ok with that. And this is why using a trust-but-verify on a specific set of compilers and ranges of compiler versions is a really good idea - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On Wed, May 4, 2016 at 11:50 PM, Theodore Ts'owrote: > Instead of arguing over who's "sane" or "insane", can we come up with > a agreed upon set of tests, and a set of compiler and compiler > versions ... I completely fail to see why tests or compiler versions should be part of the discussion. The C standard says the behaviour in certain cases is undefined, so a standard-compliant compiler can generate more-or-less any code there. As long as any of portability, reliability or security are among our goals, any code that can give undefined behaviour should be considered problematic. > But instead of arguing over what works and doesn't, let's just create > the the test set and just try it on a wide range of compilers and > architectures, hmmm? No. Let's just fix the code so that undefined behaviour cannot occur. Creating test cases for a fix and trying them on a range of systems would be useful, perhaps essential, work. Doing tests without a fix would be a complete waste of time. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On 05/04/16 21:03, Jeffrey Walton wrote: On Wed, May 4, 2016 at 11:50 PM, Theodore Ts'owrote: ... But instead of arguing over what works and doesn't, let's just create the the test set and just try it on a wide range of compilers and architectures, hmmm? What are the requirements? Here's a short list: * No undefined behavior - important because the compiler writers use the C standard * Compiles to native "rotate IMMEDIATE" if the rotate amount is a "constant expression" and the machine provides it - translates to a native rotate instruction if available - "rotate IMM" can be 3 times faster than "rotate REG" - do any architectures *not* provide a rotate? * Compiles to native "rotate REGISTER" if the rotate is variable and the machine provides it - do any architectures *not* provide a rotate? * Constant time - important to high-integrity code - Non-security code paths probably don't care Maybe the first thing to do is provide a different rotates for the constant-time requirement when its in effect? The disagreement here is the priority between these points. In my very strong opinion, "no undefined behavior" per the C standard is way less important than the others; what matters is what gcc and the other compilers we care about do. The kernel relies on various versions of C-standard-undefined behavior *all over the place*; for one thing sizeof(void *) == sizeof(size_t) == sizeof(unsigned long)!! but they are well-defined in the subcontext we care about. (And no, not all architectures provide a rotate instruction.) -hpa -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On Wed, May 4, 2016 at 11:50 PM, Theodore Ts'owrote: > ... > But instead of arguing over what works and doesn't, let's just create > the the test set and just try it on a wide range of compilers and > architectures, hmmm? What are the requirements? Here's a short list: * No undefined behavior - important because the compiler writers use the C standard * Compiles to native "rotate IMMEDIATE" if the rotate amount is a "constant expression" and the machine provides it - translates to a native rotate instruction if available - "rotate IMM" can be 3 times faster than "rotate REG" - do any architectures *not* provide a rotate? * Compiles to native "rotate REGISTER" if the rotate is variable and the machine provides it - do any architectures *not* provide a rotate? * Constant time - important to high-integrity code - Non-security code paths probably don't care Maybe the first thing to do is provide a different rotates for the constant-time requirement when its in effect? Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
Instead of arguing over who's "sane" or "insane", can we come up with a agreed upon set of tests, and a set of compiler and compiler versions for which these tests must achieve at least *working* code? Bonus points if they achieve optimal code, but what's important is that for a wide range of GCC versions (from ancient RHEL distributions to bleeding edge gcc 5.x compilers) this *must* work. >From my perspective, clang and ICC producing corret code is a very nice to have, but most shops I know of don't yet assume that clang produces code that is trustworthy for production systems, although it *is* great for as far as generating compiler warnings to find potential bugs. But instead of arguing over what works and doesn't, let's just create the the test set and just try it on a wide range of compilers and architectures, hmmm? - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
>>> So you are actually saying outright that we should sacrifice *actual* >>portability in favor of *theoretical* portability? What kind of >>twilight zone did we just step into?! >> >>I'm not sure what you mean. It will be well defined on all platforms. >>Clang may not recognize the pattern, which means they could run >>slower. GCC and ICC will be fine. >> >>Slower but correct code is what you have to live with until the Clang >>dev's fix their compiler. >> >>Its kind of like what Dr. Jon Bentley said: "If it doesn't have to be >>correct, I can make it as fast as you'd like it to be". > > The current code works on all compilers we care about. The code you propose > does not; it doesn't work on anything but very recent versions of our > flagship target compiler, and pretty your own admission might even cause > security hazards in the kernel if compiled on clang. I'm not sure how you're arriving at the conclusion the code does not work. > That qualifies as insane in my book. OK, thanks. I see the kernel is providing IPSec, SSL/TLS, etc. You can make SSL/TLS run faster by using aNULL and eNULL. Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On May 4, 2016 7:54:12 PM PDT, Jeffrey Waltonwrote: >On Wed, May 4, 2016 at 10:41 PM, H. Peter Anvin wrote: >> On May 4, 2016 6:35:44 PM PDT, Jeffrey Walton >wrote: >>>On Wed, May 4, 2016 at 5:52 PM, John Denker wrote: On 05/04/2016 02:42 PM, I wrote: > I find it very odd that the other seven functions were not > upgraded. I suggest the attached fix-others.diff would make > things more consistent. Here's a replacement patch. ... >>> >>>+1, commit it. >>> >>>Its good for three additional reasons. First, this change means the >>>kernel is teaching the next generation the correct way to do things. >>>Many developers aspire to be kernel hackers, and they sometimes use >>>the code from bitops.h. I've actually run across the code in >>>production during an audit where the developers cited bitops.h. >>> >>>Second, it preserves a "silent and dark" cockpit during analysis. >That >>>is, when analysis is run, no findings are generated. Auditors and >>>security folks like quiet tools, much like the way pilots like their >>>cockpits (flashing lights and sounding buzzers usually means >something >>>is wrong). >>> >>>Third, the pattern is recognized by the major compilers, so the >kernel >>>should not have any trouble when porting any of the compilers. I >often >>>use multiple compiler to tease out implementation defined behavior in >>>a effort to achieve greater portability. Here are the citations to >>>ensure the kernel is safe with the pattern: >>> >>> * GCC: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157 >>> * ICC: http://software.intel.com/en-us/forums/topic/580884 >>> >>>However, Clang may cause trouble because they don't want the >>>responsibility of recognizing the pattern: >>> >>> * https://llvm.org/bugs/show_bug.cgi?id=24226#c8 >>> >>>Instead, they provide a defective rotate. The "defect" here is its >>>non-constant time due to the branch, so it may not be suitable for >>>high-integrity or high-assurance code like linux-crypto: >>> >>> * https://llvm.org/bugs/show_bug.cgi?id=24226#c5 >>> >>>Jeff >> >> So you are actually saying outright that we should sacrifice *actual* >portability in favor of *theoretical* portability? What kind of >twilight zone did we just step into?! > >I'm not sure what you mean. It will be well defined on all platforms. >Clang may not recognize the pattern, which means they could run >slower. GCC and ICC will be fine. > >Slower but correct code is what you have to live with until the Clang >dev's fix their compiler. > >Its kind of like what Dr. Jon Bentley said: "If it doesn't have to be >correct, I can make it as fast as you'd like it to be". > >Jeff The current code works on all compilers we care about. The code you propose does not; it doesn't work on anything but very recent versions of our flagship target compiler, and pretty your own admission might even cause security hazards in the kernel if compiled on clang. That qualifies as insane in my book. The church code is de facto portable with the intended outcome, the one you propose is not. -- Sent from my Android device with K-9 Mail. Please excuse brevity and formatting. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On Wed, May 4, 2016 at 10:41 PM, H. Peter Anvinwrote: > On May 4, 2016 6:35:44 PM PDT, Jeffrey Walton wrote: >>On Wed, May 4, 2016 at 5:52 PM, John Denker wrote: >>> On 05/04/2016 02:42 PM, I wrote: >>> I find it very odd that the other seven functions were not upgraded. I suggest the attached fix-others.diff would make things more consistent. >>> >>> Here's a replacement patch. >>> ... >> >>+1, commit it. >> >>Its good for three additional reasons. First, this change means the >>kernel is teaching the next generation the correct way to do things. >>Many developers aspire to be kernel hackers, and they sometimes use >>the code from bitops.h. I've actually run across the code in >>production during an audit where the developers cited bitops.h. >> >>Second, it preserves a "silent and dark" cockpit during analysis. That >>is, when analysis is run, no findings are generated. Auditors and >>security folks like quiet tools, much like the way pilots like their >>cockpits (flashing lights and sounding buzzers usually means something >>is wrong). >> >>Third, the pattern is recognized by the major compilers, so the kernel >>should not have any trouble when porting any of the compilers. I often >>use multiple compiler to tease out implementation defined behavior in >>a effort to achieve greater portability. Here are the citations to >>ensure the kernel is safe with the pattern: >> >> * GCC: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157 >> * ICC: http://software.intel.com/en-us/forums/topic/580884 >> >>However, Clang may cause trouble because they don't want the >>responsibility of recognizing the pattern: >> >> * https://llvm.org/bugs/show_bug.cgi?id=24226#c8 >> >>Instead, they provide a defective rotate. The "defect" here is its >>non-constant time due to the branch, so it may not be suitable for >>high-integrity or high-assurance code like linux-crypto: >> >> * https://llvm.org/bugs/show_bug.cgi?id=24226#c5 >> >>Jeff > > So you are actually saying outright that we should sacrifice *actual* > portability in favor of *theoretical* portability? What kind of twilight > zone did we just step into?! I'm not sure what you mean. It will be well defined on all platforms. Clang may not recognize the pattern, which means they could run slower. GCC and ICC will be fine. Slower but correct code is what you have to live with until the Clang dev's fix their compiler. Its kind of like what Dr. Jon Bentley said: "If it doesn't have to be correct, I can make it as fast as you'd like it to be". Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On May 4, 2016 6:35:44 PM PDT, Jeffrey Waltonwrote: >On Wed, May 4, 2016 at 5:52 PM, John Denker wrote: >> On 05/04/2016 02:42 PM, I wrote: >> >>> I find it very odd that the other seven functions were not >>> upgraded. I suggest the attached fix-others.diff would make >>> things more consistent. >> >> Here's a replacement patch. >> ... > >+1, commit it. > >Its good for three additional reasons. First, this change means the >kernel is teaching the next generation the correct way to do things. >Many developers aspire to be kernel hackers, and they sometimes use >the code from bitops.h. I've actually run across the code in >production during an audit where the developers cited bitops.h. > >Second, it preserves a "silent and dark" cockpit during analysis. That >is, when analysis is run, no findings are generated. Auditors and >security folks like quiet tools, much like the way pilots like their >cockpits (flashing lights and sounding buzzers usually means something >is wrong). > >Third, the pattern is recognized by the major compilers, so the kernel >should not have any trouble when porting any of the compilers. I often >use multiple compiler to tease out implementation defined behavior in >a effort to achieve greater portability. Here are the citations to >ensure the kernel is safe with the pattern: > > * GCC: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157 > * ICC: http://software.intel.com/en-us/forums/topic/580884 > >However, Clang may cause trouble because they don't want the >responsibility of recognizing the pattern: > > * https://llvm.org/bugs/show_bug.cgi?id=24226#c8 > >Instead, they provide a defective rotate. The "defect" here is its >non-constant time due to the branch, so it may not be suitable for >high-integrity or high-assurance code like linux-crypto: > > * https://llvm.org/bugs/show_bug.cgi?id=24226#c5 > >Jeff So you are actually saying outright that we should sacrifice *actual* portability in favor of *theoretical* portability? What kind of twilight zone did we just step into?! -- Sent from my Android device with K-9 Mail. Please excuse brevity and formatting. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On Wed, May 4, 2016 at 5:52 PM, John Denkerwrote: > On 05/04/2016 02:42 PM, I wrote: > >> I find it very odd that the other seven functions were not >> upgraded. I suggest the attached fix-others.diff would make >> things more consistent. > > Here's a replacement patch. > ... +1, commit it. Its good for three additional reasons. First, this change means the kernel is teaching the next generation the correct way to do things. Many developers aspire to be kernel hackers, and they sometimes use the code from bitops.h. I've actually run across the code in production during an audit where the developers cited bitops.h. Second, it preserves a "silent and dark" cockpit during analysis. That is, when analysis is run, no findings are generated. Auditors and security folks like quiet tools, much like the way pilots like their cockpits (flashing lights and sounding buzzers usually means something is wrong). Third, the pattern is recognized by the major compilers, so the kernel should not have any trouble when porting any of the compilers. I often use multiple compiler to tease out implementation defined behavior in a effort to achieve greater portability. Here are the citations to ensure the kernel is safe with the pattern: * GCC: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157 * ICC: http://software.intel.com/en-us/forums/topic/580884 However, Clang may cause trouble because they don't want the responsibility of recognizing the pattern: * https://llvm.org/bugs/show_bug.cgi?id=24226#c8 Instead, they provide a defective rotate. The "defect" here is its non-constant time due to the branch, so it may not be suitable for high-integrity or high-assurance code like linux-crypto: * https://llvm.org/bugs/show_bug.cgi?id=24226#c5 Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On 05/04/2016 02:42 PM, I wrote: > I find it very odd that the other seven functions were not > upgraded. I suggest the attached fix-others.diff would make > things more consistent. Here's a replacement patch. Same idea, less brain damage. Sorry for the confusion. commit ba83b16d8430ee6104aa1feeed4ff7a82b02747a Author: John DenkerDate: Wed May 4 13:55:51 2016 -0700 Make ror64, rol64, ror32, ror16, rol16, ror8, and rol8 consistent with rol32 in their handling of shifting by a zero amount. Same overall rationale as in d7e35dfa, just more consistently applied. Beware that shifting by an amount >= the number of bits in the word remains Undefined Behavior. This should be either documented or fixed. It could be fixed easily enough. diff --git a/include/linux/bitops.h b/include/linux/bitops.h index defeaac..90f389b 100644 --- a/include/linux/bitops.h +++ b/include/linux/bitops.h @@ -87,7 +87,7 @@ static __always_inline unsigned long hweight_long(unsigned long w) */ static inline __u64 rol64(__u64 word, unsigned int shift) { - return (word << shift) | (word >> (64 - shift)); + return (word << shift) | (word >> ((-shift) & 63)); } /** @@ -97,7 +97,7 @@ static inline __u64 rol64(__u64 word, unsigned int shift) */ static inline __u64 ror64(__u64 word, unsigned int shift) { - return (word >> shift) | (word << (64 - shift)); + return (word >> shift) | (word << ((-shift) & 63)); } /** @@ -117,7 +117,7 @@ static inline __u32 rol32(__u32 word, unsigned int shift) */ static inline __u32 ror32(__u32 word, unsigned int shift) { - return (word >> shift) | (word << (32 - shift)); + return (word >> shift) | (word << ((-shift) & 31)); } /** @@ -127,7 +127,7 @@ static inline __u32 ror32(__u32 word, unsigned int shift) */ static inline __u16 rol16(__u16 word, unsigned int shift) { - return (word << shift) | (word >> (16 - shift)); + return (word << shift) | (word >> ((-shift) & 15)); } /** @@ -137,7 +137,7 @@ static inline __u16 rol16(__u16 word, unsigned int shift) */ static inline __u16 ror16(__u16 word, unsigned int shift) { - return (word >> shift) | (word << (16 - shift)); + return (word >> shift) | (word << ((-shift) & 15)); } /** @@ -147,7 +147,7 @@ static inline __u16 ror16(__u16 word, unsigned int shift) */ static inline __u8 rol8(__u8 word, unsigned int shift) { - return (word << shift) | (word >> (8 - shift)); + return (word << shift) | (word >> ((-shift) & 7)); } /** @@ -157,7 +157,7 @@ static inline __u8 rol8(__u8 word, unsigned int shift) */ static inline __u8 ror8(__u8 word, unsigned int shift) { - return (word >> shift) | (word << (8 - shift)); + return (word >> shift) | (word << ((-shift) & 7)); } /**