80-bit collision resistence because of 80-bit x87 registers?












8












$begingroup$


This is just a curious question, and it probably doesn't belong here anyway, and I'm just being bold asking it here.



80-bit used to be considered an adequate level of security, Skipjack and SHA1 were designed to be 80-bit-secure. But why 80 bits? Isn't 96 bits better because it's a multiple of 32 and gives a higher margin?



Does the choice of 80 bits have anything to do with the fact that the 8087 processor has a 80-bit floating-point register as part of the design?










share|improve this question











$endgroup$








  • 8




    $begingroup$
    In short, no, because the algorithms we're looking at work with integers, not floating point. It's an interesting coincidence, but nothing more.
    $endgroup$
    – Toby Speight
    Feb 21 at 15:40










  • $begingroup$
    x87 registers are only usable for FP operations, with a 64-bit significand (aka mantissa), 15-bit exponent, and 1 sign bit. en.wikipedia.org/wiki/Extended_precision. No shifts, OR, or XOR of the FP bit-patterns. The MMX integer SIMD registers alias the x87 registers (so OSes don't have any new architectural state to save/restore; legacy fsave/frstor already worked), but are only 64 bits wide. (SSE/SSE2 XMM registers are 128-bit wide and independent, so they did need new OS support for context switches).
    $endgroup$
    – Peter Cordes
    Feb 21 at 19:32








  • 3




    $begingroup$
    SHA1 is not designed to be implemented using two 80 bit registers. Rather it is designed to be implemented using five 32 bit registers.
    $endgroup$
    – kasperd
    Feb 21 at 22:49
















8












$begingroup$


This is just a curious question, and it probably doesn't belong here anyway, and I'm just being bold asking it here.



80-bit used to be considered an adequate level of security, Skipjack and SHA1 were designed to be 80-bit-secure. But why 80 bits? Isn't 96 bits better because it's a multiple of 32 and gives a higher margin?



Does the choice of 80 bits have anything to do with the fact that the 8087 processor has a 80-bit floating-point register as part of the design?










share|improve this question











$endgroup$








  • 8




    $begingroup$
    In short, no, because the algorithms we're looking at work with integers, not floating point. It's an interesting coincidence, but nothing more.
    $endgroup$
    – Toby Speight
    Feb 21 at 15:40










  • $begingroup$
    x87 registers are only usable for FP operations, with a 64-bit significand (aka mantissa), 15-bit exponent, and 1 sign bit. en.wikipedia.org/wiki/Extended_precision. No shifts, OR, or XOR of the FP bit-patterns. The MMX integer SIMD registers alias the x87 registers (so OSes don't have any new architectural state to save/restore; legacy fsave/frstor already worked), but are only 64 bits wide. (SSE/SSE2 XMM registers are 128-bit wide and independent, so they did need new OS support for context switches).
    $endgroup$
    – Peter Cordes
    Feb 21 at 19:32








  • 3




    $begingroup$
    SHA1 is not designed to be implemented using two 80 bit registers. Rather it is designed to be implemented using five 32 bit registers.
    $endgroup$
    – kasperd
    Feb 21 at 22:49














8












8








8


1



$begingroup$


This is just a curious question, and it probably doesn't belong here anyway, and I'm just being bold asking it here.



80-bit used to be considered an adequate level of security, Skipjack and SHA1 were designed to be 80-bit-secure. But why 80 bits? Isn't 96 bits better because it's a multiple of 32 and gives a higher margin?



Does the choice of 80 bits have anything to do with the fact that the 8087 processor has a 80-bit floating-point register as part of the design?










share|improve this question











$endgroup$




This is just a curious question, and it probably doesn't belong here anyway, and I'm just being bold asking it here.



80-bit used to be considered an adequate level of security, Skipjack and SHA1 were designed to be 80-bit-secure. But why 80 bits? Isn't 96 bits better because it's a multiple of 32 and gives a higher margin?



Does the choice of 80 bits have anything to do with the fact that the 8087 processor has a 80-bit floating-point register as part of the design?







key-size history






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Feb 21 at 10:58









kodlu

9,00511330




9,00511330










asked Feb 21 at 8:22









DannyNiuDannyNiu

1,2611628




1,2611628








  • 8




    $begingroup$
    In short, no, because the algorithms we're looking at work with integers, not floating point. It's an interesting coincidence, but nothing more.
    $endgroup$
    – Toby Speight
    Feb 21 at 15:40










  • $begingroup$
    x87 registers are only usable for FP operations, with a 64-bit significand (aka mantissa), 15-bit exponent, and 1 sign bit. en.wikipedia.org/wiki/Extended_precision. No shifts, OR, or XOR of the FP bit-patterns. The MMX integer SIMD registers alias the x87 registers (so OSes don't have any new architectural state to save/restore; legacy fsave/frstor already worked), but are only 64 bits wide. (SSE/SSE2 XMM registers are 128-bit wide and independent, so they did need new OS support for context switches).
    $endgroup$
    – Peter Cordes
    Feb 21 at 19:32








  • 3




    $begingroup$
    SHA1 is not designed to be implemented using two 80 bit registers. Rather it is designed to be implemented using five 32 bit registers.
    $endgroup$
    – kasperd
    Feb 21 at 22:49














  • 8




    $begingroup$
    In short, no, because the algorithms we're looking at work with integers, not floating point. It's an interesting coincidence, but nothing more.
    $endgroup$
    – Toby Speight
    Feb 21 at 15:40










  • $begingroup$
    x87 registers are only usable for FP operations, with a 64-bit significand (aka mantissa), 15-bit exponent, and 1 sign bit. en.wikipedia.org/wiki/Extended_precision. No shifts, OR, or XOR of the FP bit-patterns. The MMX integer SIMD registers alias the x87 registers (so OSes don't have any new architectural state to save/restore; legacy fsave/frstor already worked), but are only 64 bits wide. (SSE/SSE2 XMM registers are 128-bit wide and independent, so they did need new OS support for context switches).
    $endgroup$
    – Peter Cordes
    Feb 21 at 19:32








  • 3




    $begingroup$
    SHA1 is not designed to be implemented using two 80 bit registers. Rather it is designed to be implemented using five 32 bit registers.
    $endgroup$
    – kasperd
    Feb 21 at 22:49








8




8




$begingroup$
In short, no, because the algorithms we're looking at work with integers, not floating point. It's an interesting coincidence, but nothing more.
$endgroup$
– Toby Speight
Feb 21 at 15:40




$begingroup$
In short, no, because the algorithms we're looking at work with integers, not floating point. It's an interesting coincidence, but nothing more.
$endgroup$
– Toby Speight
Feb 21 at 15:40












$begingroup$
x87 registers are only usable for FP operations, with a 64-bit significand (aka mantissa), 15-bit exponent, and 1 sign bit. en.wikipedia.org/wiki/Extended_precision. No shifts, OR, or XOR of the FP bit-patterns. The MMX integer SIMD registers alias the x87 registers (so OSes don't have any new architectural state to save/restore; legacy fsave/frstor already worked), but are only 64 bits wide. (SSE/SSE2 XMM registers are 128-bit wide and independent, so they did need new OS support for context switches).
$endgroup$
– Peter Cordes
Feb 21 at 19:32






$begingroup$
x87 registers are only usable for FP operations, with a 64-bit significand (aka mantissa), 15-bit exponent, and 1 sign bit. en.wikipedia.org/wiki/Extended_precision. No shifts, OR, or XOR of the FP bit-patterns. The MMX integer SIMD registers alias the x87 registers (so OSes don't have any new architectural state to save/restore; legacy fsave/frstor already worked), but are only 64 bits wide. (SSE/SSE2 XMM registers are 128-bit wide and independent, so they did need new OS support for context switches).
$endgroup$
– Peter Cordes
Feb 21 at 19:32






3




3




$begingroup$
SHA1 is not designed to be implemented using two 80 bit registers. Rather it is designed to be implemented using five 32 bit registers.
$endgroup$
– kasperd
Feb 21 at 22:49




$begingroup$
SHA1 is not designed to be implemented using two 80 bit registers. Rather it is designed to be implemented using five 32 bit registers.
$endgroup$
– kasperd
Feb 21 at 22:49










4 Answers
4






active

oldest

votes


















10












$begingroup$

Coprocessors are designed for improved performance in a certain case, and in the case of fixed-width mathematics, I do not believe you would see a performance increase.



I am quite sure that 80-bits is simply because it is 10, 8-bit words, and not that it is targeting the 80-bit registers in a FPU. Primarily, it would be inconvenient to use an FPU for this case due to the instruction layout. In the case of Skipjack or a Feistel network in general, I do not know of any easy way to do the block swap without pulling the words out of the FPU back to the CPU to do the swap because the FPU hardware is designed around mantissa functions, not shifts and XORs. You could use the FPU for intermediate storage, but because the x87 (this is particular case that is very x86 specific), you pull the 10-byte sequence from the stack, which would be more of a cost than just keeping it all in the integer unit.



Another note of security margins and Skipjack, it was designed for a minimally viable VLSI implementation. If you were going to put something on an IC circa 1996, you'd probably lean toward 80-bits over 88 or 96, or larger. MPEG-1, 2, 4 etc all had choices that were sub-optimal mathematically but the decoder ICs needed to be viable as a VLSI implementation. At meetings, this is always a constraint that comes up. At NIST 8114, we've had the discussions but I've never seen these discussions formalized. In power constrained computing, such as passively powered RFID, I still make engineering choices that are sub-optimal as far as ideal cryptography because bits cost money to make, power to use, and I don't have the luxury of increasing IC costs or power consumption. Encryption often takes a backseat to economics in the same way that security does to convenience.






share|improve this answer









$endgroup$





















    7












    $begingroup$

    The original SHA-1 and Skipjack specifications did not provide a justification for using a 80-bit key size, so we can only speculate about the reasons. However, it is important to understand that from a historical basis, an 80-bit key was considered adequate (barely) to be secure against exhaustive search for a few decades. It was clear that a 64-bit key size was not adequate, and a 128-bit keylength was more than needed. My own speculation is that 80 bits were chosen based on a calculation and extrapolation about how long a key was needed, to ensure a reasonable level of security against exhaustive keysearch for the next few decades.



    The independent review of Skipjack is consistent with this viewpoint. Their executive summary states:




    Under an assumption that the cost of processing power is halved
    every eighteen months, it will be 36 years before the cost of
    breaking SKIPJACK by exhaustive search will be equal to the cost
    of breaking DES today. Thus, there is no significant risk that
    SKIPJACK will be broken by exhaustive search in the next 30-40
    years.



    Source: SKIPJACK Review: Interim Report. Ernest F. Brickell, Dorothy E. Denning, Stephen T. Kent, David P. Maher, Walter Tuchman. July 28, 1993.




    Why not a longer key? Well, there are two reasons:




    1. A longer key (or security to greater than $2^{80}$ level) would leave you with a slower algorithm. For instance, SHA-1 would have been a lot slower if it had been designed to provide a 128-bit level of security, rather than a 80-bit level. Moreover, performance was a big deal at the time -- much more so than today. Developers routinely shied away from using cryptography because of fears over its performance impact. So, choosing an unnecessarily long keylength would have made the algorithm even slower, possibly leading to even less use of cryptography, which overall might have been worse for security. As a 80-bit level was considered adequate, there were good reasons not to make the algorithm slower than needed by seeking a longer key.


    2. In the particular case of Skipjack, it also seems likely to me that the NSA did not choose a longer key length to avoid contributing to the spread of strong encryption. Remember that Skipjack was designed during the height of the crypto wars, when the NSA's policy was to limit spread of strong cryptography. Also, Skipjack was designed to be part of the Clipper key escrow initiative. I imagine the NSA expected that the Skipjack algorithm would become public, and they didn't want to share their best, strongest encryption technology with the world. Skipjack's design is interesting in that its key length is "baked into" the design of the cipher: it isn't obvious how to increase its key length, without losing its security properties, and multiple aspects of the cipher (the key length, the number of rounds, etc.) all appear to have been chosen carefully to provide exactly a $2^{80}$ level of security -- no more, and no less. So, the NSA might have chosen a 80-bit key as a key length that is adequate to support the purposes of the Clipper key escrow initiative (or to support commercial purposes), while at the same time being no longer than necessary (to avoid contributing to the proliferation of cryptography among the enemies they wanted to spy on).



    Finally, I would like to point out that the conclusion of approximately 80-bit keys being (barely) adequate was by no means out of the mainstream. At the time, I think a 80-bit level of security was viewed by many as sufficient and a reasonable engineering choice. For instance, an analysis done Lenstra and Verheul about 10 years later recommended symmetric keys of 86 bits and hash functions of 172 bits, to achieve security until 2020; this was often summarized as 80 bits is about a sweet spot. See Selecting Cryptographic Key Sizes, Arjen K. Lenstra and Eric R. Verheul, J. Cryptology, vol 14, 2001, pp.255-293.






    share|improve this answer











    $endgroup$





















      5












      $begingroup$

      To get 80 bit security for a Hash function, you need a hash with output bitlength 160 bits due to the birthday problem and collision resistance. Note that $160=5times 32.$



      So, the 80 bits was convenient as security level for Hashes since they then equalled the existing idea of 80 bits as being a good security level for symmetric key at that time. The fact that AES was already 128 bits was due to inbuilt extra margins to survive well into the future.






      share|improve this answer









      $endgroup$





















        5












        $begingroup$

        Skipjack rotates the text being encrypted by 16 bits each step, and cycles though the key 16 bits at a time. If the key length were not a multiple of 16, that would complicate software implementations. If the key length were a multiple of 64, every word of key would be used only when acting on a particular word in the block being encrypted. If the key were an odd multiple of 32 bits, then within each 32 bits of key, the first half would be used only with the first and third 16-bit chunks of each block, while the second half would be used only with the second and fourth.



        Thus, reasonable choices for key length would be 48, 80, 112, or 144. Of those, 80 was considered the most practical. A key length of 48 would have been too short. While a 64-bit key might have been considered "enough" for the time, using a key that was exactly 64 bits would expose severe structural weaknesses. That leaves 80 bits as the smallest (and thus most convenient) key that would meet all requirements.






        share|improve this answer









        $endgroup$













          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "281"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f67491%2f80-bit-collision-resistence-because-of-80-bit-x87-registers%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          4 Answers
          4






          active

          oldest

          votes








          4 Answers
          4






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          10












          $begingroup$

          Coprocessors are designed for improved performance in a certain case, and in the case of fixed-width mathematics, I do not believe you would see a performance increase.



          I am quite sure that 80-bits is simply because it is 10, 8-bit words, and not that it is targeting the 80-bit registers in a FPU. Primarily, it would be inconvenient to use an FPU for this case due to the instruction layout. In the case of Skipjack or a Feistel network in general, I do not know of any easy way to do the block swap without pulling the words out of the FPU back to the CPU to do the swap because the FPU hardware is designed around mantissa functions, not shifts and XORs. You could use the FPU for intermediate storage, but because the x87 (this is particular case that is very x86 specific), you pull the 10-byte sequence from the stack, which would be more of a cost than just keeping it all in the integer unit.



          Another note of security margins and Skipjack, it was designed for a minimally viable VLSI implementation. If you were going to put something on an IC circa 1996, you'd probably lean toward 80-bits over 88 or 96, or larger. MPEG-1, 2, 4 etc all had choices that were sub-optimal mathematically but the decoder ICs needed to be viable as a VLSI implementation. At meetings, this is always a constraint that comes up. At NIST 8114, we've had the discussions but I've never seen these discussions formalized. In power constrained computing, such as passively powered RFID, I still make engineering choices that are sub-optimal as far as ideal cryptography because bits cost money to make, power to use, and I don't have the luxury of increasing IC costs or power consumption. Encryption often takes a backseat to economics in the same way that security does to convenience.






          share|improve this answer









          $endgroup$


















            10












            $begingroup$

            Coprocessors are designed for improved performance in a certain case, and in the case of fixed-width mathematics, I do not believe you would see a performance increase.



            I am quite sure that 80-bits is simply because it is 10, 8-bit words, and not that it is targeting the 80-bit registers in a FPU. Primarily, it would be inconvenient to use an FPU for this case due to the instruction layout. In the case of Skipjack or a Feistel network in general, I do not know of any easy way to do the block swap without pulling the words out of the FPU back to the CPU to do the swap because the FPU hardware is designed around mantissa functions, not shifts and XORs. You could use the FPU for intermediate storage, but because the x87 (this is particular case that is very x86 specific), you pull the 10-byte sequence from the stack, which would be more of a cost than just keeping it all in the integer unit.



            Another note of security margins and Skipjack, it was designed for a minimally viable VLSI implementation. If you were going to put something on an IC circa 1996, you'd probably lean toward 80-bits over 88 or 96, or larger. MPEG-1, 2, 4 etc all had choices that were sub-optimal mathematically but the decoder ICs needed to be viable as a VLSI implementation. At meetings, this is always a constraint that comes up. At NIST 8114, we've had the discussions but I've never seen these discussions formalized. In power constrained computing, such as passively powered RFID, I still make engineering choices that are sub-optimal as far as ideal cryptography because bits cost money to make, power to use, and I don't have the luxury of increasing IC costs or power consumption. Encryption often takes a backseat to economics in the same way that security does to convenience.






            share|improve this answer









            $endgroup$
















              10












              10








              10





              $begingroup$

              Coprocessors are designed for improved performance in a certain case, and in the case of fixed-width mathematics, I do not believe you would see a performance increase.



              I am quite sure that 80-bits is simply because it is 10, 8-bit words, and not that it is targeting the 80-bit registers in a FPU. Primarily, it would be inconvenient to use an FPU for this case due to the instruction layout. In the case of Skipjack or a Feistel network in general, I do not know of any easy way to do the block swap without pulling the words out of the FPU back to the CPU to do the swap because the FPU hardware is designed around mantissa functions, not shifts and XORs. You could use the FPU for intermediate storage, but because the x87 (this is particular case that is very x86 specific), you pull the 10-byte sequence from the stack, which would be more of a cost than just keeping it all in the integer unit.



              Another note of security margins and Skipjack, it was designed for a minimally viable VLSI implementation. If you were going to put something on an IC circa 1996, you'd probably lean toward 80-bits over 88 or 96, or larger. MPEG-1, 2, 4 etc all had choices that were sub-optimal mathematically but the decoder ICs needed to be viable as a VLSI implementation. At meetings, this is always a constraint that comes up. At NIST 8114, we've had the discussions but I've never seen these discussions formalized. In power constrained computing, such as passively powered RFID, I still make engineering choices that are sub-optimal as far as ideal cryptography because bits cost money to make, power to use, and I don't have the luxury of increasing IC costs or power consumption. Encryption often takes a backseat to economics in the same way that security does to convenience.






              share|improve this answer









              $endgroup$



              Coprocessors are designed for improved performance in a certain case, and in the case of fixed-width mathematics, I do not believe you would see a performance increase.



              I am quite sure that 80-bits is simply because it is 10, 8-bit words, and not that it is targeting the 80-bit registers in a FPU. Primarily, it would be inconvenient to use an FPU for this case due to the instruction layout. In the case of Skipjack or a Feistel network in general, I do not know of any easy way to do the block swap without pulling the words out of the FPU back to the CPU to do the swap because the FPU hardware is designed around mantissa functions, not shifts and XORs. You could use the FPU for intermediate storage, but because the x87 (this is particular case that is very x86 specific), you pull the 10-byte sequence from the stack, which would be more of a cost than just keeping it all in the integer unit.



              Another note of security margins and Skipjack, it was designed for a minimally viable VLSI implementation. If you were going to put something on an IC circa 1996, you'd probably lean toward 80-bits over 88 or 96, or larger. MPEG-1, 2, 4 etc all had choices that were sub-optimal mathematically but the decoder ICs needed to be viable as a VLSI implementation. At meetings, this is always a constraint that comes up. At NIST 8114, we've had the discussions but I've never seen these discussions formalized. In power constrained computing, such as passively powered RFID, I still make engineering choices that are sub-optimal as far as ideal cryptography because bits cost money to make, power to use, and I don't have the luxury of increasing IC costs or power consumption. Encryption often takes a backseat to economics in the same way that security does to convenience.







              share|improve this answer












              share|improve this answer



              share|improve this answer










              answered Feb 21 at 11:04









              b degnanb degnan

              2,0081728




              2,0081728























                  7












                  $begingroup$

                  The original SHA-1 and Skipjack specifications did not provide a justification for using a 80-bit key size, so we can only speculate about the reasons. However, it is important to understand that from a historical basis, an 80-bit key was considered adequate (barely) to be secure against exhaustive search for a few decades. It was clear that a 64-bit key size was not adequate, and a 128-bit keylength was more than needed. My own speculation is that 80 bits were chosen based on a calculation and extrapolation about how long a key was needed, to ensure a reasonable level of security against exhaustive keysearch for the next few decades.



                  The independent review of Skipjack is consistent with this viewpoint. Their executive summary states:




                  Under an assumption that the cost of processing power is halved
                  every eighteen months, it will be 36 years before the cost of
                  breaking SKIPJACK by exhaustive search will be equal to the cost
                  of breaking DES today. Thus, there is no significant risk that
                  SKIPJACK will be broken by exhaustive search in the next 30-40
                  years.



                  Source: SKIPJACK Review: Interim Report. Ernest F. Brickell, Dorothy E. Denning, Stephen T. Kent, David P. Maher, Walter Tuchman. July 28, 1993.




                  Why not a longer key? Well, there are two reasons:




                  1. A longer key (or security to greater than $2^{80}$ level) would leave you with a slower algorithm. For instance, SHA-1 would have been a lot slower if it had been designed to provide a 128-bit level of security, rather than a 80-bit level. Moreover, performance was a big deal at the time -- much more so than today. Developers routinely shied away from using cryptography because of fears over its performance impact. So, choosing an unnecessarily long keylength would have made the algorithm even slower, possibly leading to even less use of cryptography, which overall might have been worse for security. As a 80-bit level was considered adequate, there were good reasons not to make the algorithm slower than needed by seeking a longer key.


                  2. In the particular case of Skipjack, it also seems likely to me that the NSA did not choose a longer key length to avoid contributing to the spread of strong encryption. Remember that Skipjack was designed during the height of the crypto wars, when the NSA's policy was to limit spread of strong cryptography. Also, Skipjack was designed to be part of the Clipper key escrow initiative. I imagine the NSA expected that the Skipjack algorithm would become public, and they didn't want to share their best, strongest encryption technology with the world. Skipjack's design is interesting in that its key length is "baked into" the design of the cipher: it isn't obvious how to increase its key length, without losing its security properties, and multiple aspects of the cipher (the key length, the number of rounds, etc.) all appear to have been chosen carefully to provide exactly a $2^{80}$ level of security -- no more, and no less. So, the NSA might have chosen a 80-bit key as a key length that is adequate to support the purposes of the Clipper key escrow initiative (or to support commercial purposes), while at the same time being no longer than necessary (to avoid contributing to the proliferation of cryptography among the enemies they wanted to spy on).



                  Finally, I would like to point out that the conclusion of approximately 80-bit keys being (barely) adequate was by no means out of the mainstream. At the time, I think a 80-bit level of security was viewed by many as sufficient and a reasonable engineering choice. For instance, an analysis done Lenstra and Verheul about 10 years later recommended symmetric keys of 86 bits and hash functions of 172 bits, to achieve security until 2020; this was often summarized as 80 bits is about a sweet spot. See Selecting Cryptographic Key Sizes, Arjen K. Lenstra and Eric R. Verheul, J. Cryptology, vol 14, 2001, pp.255-293.






                  share|improve this answer











                  $endgroup$


















                    7












                    $begingroup$

                    The original SHA-1 and Skipjack specifications did not provide a justification for using a 80-bit key size, so we can only speculate about the reasons. However, it is important to understand that from a historical basis, an 80-bit key was considered adequate (barely) to be secure against exhaustive search for a few decades. It was clear that a 64-bit key size was not adequate, and a 128-bit keylength was more than needed. My own speculation is that 80 bits were chosen based on a calculation and extrapolation about how long a key was needed, to ensure a reasonable level of security against exhaustive keysearch for the next few decades.



                    The independent review of Skipjack is consistent with this viewpoint. Their executive summary states:




                    Under an assumption that the cost of processing power is halved
                    every eighteen months, it will be 36 years before the cost of
                    breaking SKIPJACK by exhaustive search will be equal to the cost
                    of breaking DES today. Thus, there is no significant risk that
                    SKIPJACK will be broken by exhaustive search in the next 30-40
                    years.



                    Source: SKIPJACK Review: Interim Report. Ernest F. Brickell, Dorothy E. Denning, Stephen T. Kent, David P. Maher, Walter Tuchman. July 28, 1993.




                    Why not a longer key? Well, there are two reasons:




                    1. A longer key (or security to greater than $2^{80}$ level) would leave you with a slower algorithm. For instance, SHA-1 would have been a lot slower if it had been designed to provide a 128-bit level of security, rather than a 80-bit level. Moreover, performance was a big deal at the time -- much more so than today. Developers routinely shied away from using cryptography because of fears over its performance impact. So, choosing an unnecessarily long keylength would have made the algorithm even slower, possibly leading to even less use of cryptography, which overall might have been worse for security. As a 80-bit level was considered adequate, there were good reasons not to make the algorithm slower than needed by seeking a longer key.


                    2. In the particular case of Skipjack, it also seems likely to me that the NSA did not choose a longer key length to avoid contributing to the spread of strong encryption. Remember that Skipjack was designed during the height of the crypto wars, when the NSA's policy was to limit spread of strong cryptography. Also, Skipjack was designed to be part of the Clipper key escrow initiative. I imagine the NSA expected that the Skipjack algorithm would become public, and they didn't want to share their best, strongest encryption technology with the world. Skipjack's design is interesting in that its key length is "baked into" the design of the cipher: it isn't obvious how to increase its key length, without losing its security properties, and multiple aspects of the cipher (the key length, the number of rounds, etc.) all appear to have been chosen carefully to provide exactly a $2^{80}$ level of security -- no more, and no less. So, the NSA might have chosen a 80-bit key as a key length that is adequate to support the purposes of the Clipper key escrow initiative (or to support commercial purposes), while at the same time being no longer than necessary (to avoid contributing to the proliferation of cryptography among the enemies they wanted to spy on).



                    Finally, I would like to point out that the conclusion of approximately 80-bit keys being (barely) adequate was by no means out of the mainstream. At the time, I think a 80-bit level of security was viewed by many as sufficient and a reasonable engineering choice. For instance, an analysis done Lenstra and Verheul about 10 years later recommended symmetric keys of 86 bits and hash functions of 172 bits, to achieve security until 2020; this was often summarized as 80 bits is about a sweet spot. See Selecting Cryptographic Key Sizes, Arjen K. Lenstra and Eric R. Verheul, J. Cryptology, vol 14, 2001, pp.255-293.






                    share|improve this answer











                    $endgroup$
















                      7












                      7








                      7





                      $begingroup$

                      The original SHA-1 and Skipjack specifications did not provide a justification for using a 80-bit key size, so we can only speculate about the reasons. However, it is important to understand that from a historical basis, an 80-bit key was considered adequate (barely) to be secure against exhaustive search for a few decades. It was clear that a 64-bit key size was not adequate, and a 128-bit keylength was more than needed. My own speculation is that 80 bits were chosen based on a calculation and extrapolation about how long a key was needed, to ensure a reasonable level of security against exhaustive keysearch for the next few decades.



                      The independent review of Skipjack is consistent with this viewpoint. Their executive summary states:




                      Under an assumption that the cost of processing power is halved
                      every eighteen months, it will be 36 years before the cost of
                      breaking SKIPJACK by exhaustive search will be equal to the cost
                      of breaking DES today. Thus, there is no significant risk that
                      SKIPJACK will be broken by exhaustive search in the next 30-40
                      years.



                      Source: SKIPJACK Review: Interim Report. Ernest F. Brickell, Dorothy E. Denning, Stephen T. Kent, David P. Maher, Walter Tuchman. July 28, 1993.




                      Why not a longer key? Well, there are two reasons:




                      1. A longer key (or security to greater than $2^{80}$ level) would leave you with a slower algorithm. For instance, SHA-1 would have been a lot slower if it had been designed to provide a 128-bit level of security, rather than a 80-bit level. Moreover, performance was a big deal at the time -- much more so than today. Developers routinely shied away from using cryptography because of fears over its performance impact. So, choosing an unnecessarily long keylength would have made the algorithm even slower, possibly leading to even less use of cryptography, which overall might have been worse for security. As a 80-bit level was considered adequate, there were good reasons not to make the algorithm slower than needed by seeking a longer key.


                      2. In the particular case of Skipjack, it also seems likely to me that the NSA did not choose a longer key length to avoid contributing to the spread of strong encryption. Remember that Skipjack was designed during the height of the crypto wars, when the NSA's policy was to limit spread of strong cryptography. Also, Skipjack was designed to be part of the Clipper key escrow initiative. I imagine the NSA expected that the Skipjack algorithm would become public, and they didn't want to share their best, strongest encryption technology with the world. Skipjack's design is interesting in that its key length is "baked into" the design of the cipher: it isn't obvious how to increase its key length, without losing its security properties, and multiple aspects of the cipher (the key length, the number of rounds, etc.) all appear to have been chosen carefully to provide exactly a $2^{80}$ level of security -- no more, and no less. So, the NSA might have chosen a 80-bit key as a key length that is adequate to support the purposes of the Clipper key escrow initiative (or to support commercial purposes), while at the same time being no longer than necessary (to avoid contributing to the proliferation of cryptography among the enemies they wanted to spy on).



                      Finally, I would like to point out that the conclusion of approximately 80-bit keys being (barely) adequate was by no means out of the mainstream. At the time, I think a 80-bit level of security was viewed by many as sufficient and a reasonable engineering choice. For instance, an analysis done Lenstra and Verheul about 10 years later recommended symmetric keys of 86 bits and hash functions of 172 bits, to achieve security until 2020; this was often summarized as 80 bits is about a sweet spot. See Selecting Cryptographic Key Sizes, Arjen K. Lenstra and Eric R. Verheul, J. Cryptology, vol 14, 2001, pp.255-293.






                      share|improve this answer











                      $endgroup$



                      The original SHA-1 and Skipjack specifications did not provide a justification for using a 80-bit key size, so we can only speculate about the reasons. However, it is important to understand that from a historical basis, an 80-bit key was considered adequate (barely) to be secure against exhaustive search for a few decades. It was clear that a 64-bit key size was not adequate, and a 128-bit keylength was more than needed. My own speculation is that 80 bits were chosen based on a calculation and extrapolation about how long a key was needed, to ensure a reasonable level of security against exhaustive keysearch for the next few decades.



                      The independent review of Skipjack is consistent with this viewpoint. Their executive summary states:




                      Under an assumption that the cost of processing power is halved
                      every eighteen months, it will be 36 years before the cost of
                      breaking SKIPJACK by exhaustive search will be equal to the cost
                      of breaking DES today. Thus, there is no significant risk that
                      SKIPJACK will be broken by exhaustive search in the next 30-40
                      years.



                      Source: SKIPJACK Review: Interim Report. Ernest F. Brickell, Dorothy E. Denning, Stephen T. Kent, David P. Maher, Walter Tuchman. July 28, 1993.




                      Why not a longer key? Well, there are two reasons:




                      1. A longer key (or security to greater than $2^{80}$ level) would leave you with a slower algorithm. For instance, SHA-1 would have been a lot slower if it had been designed to provide a 128-bit level of security, rather than a 80-bit level. Moreover, performance was a big deal at the time -- much more so than today. Developers routinely shied away from using cryptography because of fears over its performance impact. So, choosing an unnecessarily long keylength would have made the algorithm even slower, possibly leading to even less use of cryptography, which overall might have been worse for security. As a 80-bit level was considered adequate, there were good reasons not to make the algorithm slower than needed by seeking a longer key.


                      2. In the particular case of Skipjack, it also seems likely to me that the NSA did not choose a longer key length to avoid contributing to the spread of strong encryption. Remember that Skipjack was designed during the height of the crypto wars, when the NSA's policy was to limit spread of strong cryptography. Also, Skipjack was designed to be part of the Clipper key escrow initiative. I imagine the NSA expected that the Skipjack algorithm would become public, and they didn't want to share their best, strongest encryption technology with the world. Skipjack's design is interesting in that its key length is "baked into" the design of the cipher: it isn't obvious how to increase its key length, without losing its security properties, and multiple aspects of the cipher (the key length, the number of rounds, etc.) all appear to have been chosen carefully to provide exactly a $2^{80}$ level of security -- no more, and no less. So, the NSA might have chosen a 80-bit key as a key length that is adequate to support the purposes of the Clipper key escrow initiative (or to support commercial purposes), while at the same time being no longer than necessary (to avoid contributing to the proliferation of cryptography among the enemies they wanted to spy on).



                      Finally, I would like to point out that the conclusion of approximately 80-bit keys being (barely) adequate was by no means out of the mainstream. At the time, I think a 80-bit level of security was viewed by many as sufficient and a reasonable engineering choice. For instance, an analysis done Lenstra and Verheul about 10 years later recommended symmetric keys of 86 bits and hash functions of 172 bits, to achieve security until 2020; this was often summarized as 80 bits is about a sweet spot. See Selecting Cryptographic Key Sizes, Arjen K. Lenstra and Eric R. Verheul, J. Cryptology, vol 14, 2001, pp.255-293.







                      share|improve this answer














                      share|improve this answer



                      share|improve this answer








                      edited Feb 21 at 21:40









                      Ella Rose

                      16.4k44281




                      16.4k44281










                      answered Feb 21 at 20:07









                      D.W.D.W.

                      29.8k768146




                      29.8k768146























                          5












                          $begingroup$

                          To get 80 bit security for a Hash function, you need a hash with output bitlength 160 bits due to the birthday problem and collision resistance. Note that $160=5times 32.$



                          So, the 80 bits was convenient as security level for Hashes since they then equalled the existing idea of 80 bits as being a good security level for symmetric key at that time. The fact that AES was already 128 bits was due to inbuilt extra margins to survive well into the future.






                          share|improve this answer









                          $endgroup$


















                            5












                            $begingroup$

                            To get 80 bit security for a Hash function, you need a hash with output bitlength 160 bits due to the birthday problem and collision resistance. Note that $160=5times 32.$



                            So, the 80 bits was convenient as security level for Hashes since they then equalled the existing idea of 80 bits as being a good security level for symmetric key at that time. The fact that AES was already 128 bits was due to inbuilt extra margins to survive well into the future.






                            share|improve this answer









                            $endgroup$
















                              5












                              5








                              5





                              $begingroup$

                              To get 80 bit security for a Hash function, you need a hash with output bitlength 160 bits due to the birthday problem and collision resistance. Note that $160=5times 32.$



                              So, the 80 bits was convenient as security level for Hashes since they then equalled the existing idea of 80 bits as being a good security level for symmetric key at that time. The fact that AES was already 128 bits was due to inbuilt extra margins to survive well into the future.






                              share|improve this answer









                              $endgroup$



                              To get 80 bit security for a Hash function, you need a hash with output bitlength 160 bits due to the birthday problem and collision resistance. Note that $160=5times 32.$



                              So, the 80 bits was convenient as security level for Hashes since they then equalled the existing idea of 80 bits as being a good security level for symmetric key at that time. The fact that AES was already 128 bits was due to inbuilt extra margins to survive well into the future.







                              share|improve this answer












                              share|improve this answer



                              share|improve this answer










                              answered Feb 21 at 11:04









                              kodlukodlu

                              9,00511330




                              9,00511330























                                  5












                                  $begingroup$

                                  Skipjack rotates the text being encrypted by 16 bits each step, and cycles though the key 16 bits at a time. If the key length were not a multiple of 16, that would complicate software implementations. If the key length were a multiple of 64, every word of key would be used only when acting on a particular word in the block being encrypted. If the key were an odd multiple of 32 bits, then within each 32 bits of key, the first half would be used only with the first and third 16-bit chunks of each block, while the second half would be used only with the second and fourth.



                                  Thus, reasonable choices for key length would be 48, 80, 112, or 144. Of those, 80 was considered the most practical. A key length of 48 would have been too short. While a 64-bit key might have been considered "enough" for the time, using a key that was exactly 64 bits would expose severe structural weaknesses. That leaves 80 bits as the smallest (and thus most convenient) key that would meet all requirements.






                                  share|improve this answer









                                  $endgroup$


















                                    5












                                    $begingroup$

                                    Skipjack rotates the text being encrypted by 16 bits each step, and cycles though the key 16 bits at a time. If the key length were not a multiple of 16, that would complicate software implementations. If the key length were a multiple of 64, every word of key would be used only when acting on a particular word in the block being encrypted. If the key were an odd multiple of 32 bits, then within each 32 bits of key, the first half would be used only with the first and third 16-bit chunks of each block, while the second half would be used only with the second and fourth.



                                    Thus, reasonable choices for key length would be 48, 80, 112, or 144. Of those, 80 was considered the most practical. A key length of 48 would have been too short. While a 64-bit key might have been considered "enough" for the time, using a key that was exactly 64 bits would expose severe structural weaknesses. That leaves 80 bits as the smallest (and thus most convenient) key that would meet all requirements.






                                    share|improve this answer









                                    $endgroup$
















                                      5












                                      5








                                      5





                                      $begingroup$

                                      Skipjack rotates the text being encrypted by 16 bits each step, and cycles though the key 16 bits at a time. If the key length were not a multiple of 16, that would complicate software implementations. If the key length were a multiple of 64, every word of key would be used only when acting on a particular word in the block being encrypted. If the key were an odd multiple of 32 bits, then within each 32 bits of key, the first half would be used only with the first and third 16-bit chunks of each block, while the second half would be used only with the second and fourth.



                                      Thus, reasonable choices for key length would be 48, 80, 112, or 144. Of those, 80 was considered the most practical. A key length of 48 would have been too short. While a 64-bit key might have been considered "enough" for the time, using a key that was exactly 64 bits would expose severe structural weaknesses. That leaves 80 bits as the smallest (and thus most convenient) key that would meet all requirements.






                                      share|improve this answer









                                      $endgroup$



                                      Skipjack rotates the text being encrypted by 16 bits each step, and cycles though the key 16 bits at a time. If the key length were not a multiple of 16, that would complicate software implementations. If the key length were a multiple of 64, every word of key would be used only when acting on a particular word in the block being encrypted. If the key were an odd multiple of 32 bits, then within each 32 bits of key, the first half would be used only with the first and third 16-bit chunks of each block, while the second half would be used only with the second and fourth.



                                      Thus, reasonable choices for key length would be 48, 80, 112, or 144. Of those, 80 was considered the most practical. A key length of 48 would have been too short. While a 64-bit key might have been considered "enough" for the time, using a key that was exactly 64 bits would expose severe structural weaknesses. That leaves 80 bits as the smallest (and thus most convenient) key that would meet all requirements.







                                      share|improve this answer












                                      share|improve this answer



                                      share|improve this answer










                                      answered Feb 21 at 16:52









                                      supercatsupercat

                                      27914




                                      27914






























                                          draft saved

                                          draft discarded




















































                                          Thanks for contributing an answer to Cryptography Stack Exchange!


                                          • Please be sure to answer the question. Provide details and share your research!

                                          But avoid



                                          • Asking for help, clarification, or responding to other answers.

                                          • Making statements based on opinion; back them up with references or personal experience.


                                          Use MathJax to format equations. MathJax reference.


                                          To learn more, see our tips on writing great answers.




                                          draft saved


                                          draft discarded














                                          StackExchange.ready(
                                          function () {
                                          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f67491%2f80-bit-collision-resistence-because-of-80-bit-x87-registers%23new-answer', 'question_page');
                                          }
                                          );

                                          Post as a guest















                                          Required, but never shown





















































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown

































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown







                                          Popular posts from this blog

                                          How to change which sound is reproduced for terminal bell?

                                          Can I use Tabulator js library in my java Spring + Thymeleaf project?

                                          Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents