4 ms·

>We know we need at least like 80 bits to start to be safe against brute force. you could imagine a cipher with a computational/memory[0] intensity so high tha

by mr__y 7y ago

>We know we need at least like 80 bits to start to be safe against brute force. you could imagine a cipher with a computational/memory[0] intensity so high that the brute force attack could be practically infeasible even at lower key-sizes. I am not advocating using smaller keys, just pointing out that there is more to brute-force resistance that simply just the key-length number. (That is probably the numerology the GP was referring to) [0]Since memory intensity instead of pure computational intensity seems to be employed by some hashing alghorithms I wonder is that would be possible block ciphers as well. The way I understand this, it makes ASIC/FPGA brute-forcing a lot harder/expensive

mlyle 7y ago
> you could imagine a cipher with a computational/memory[0] intensity so high that the brute force attack could be practically infeasible even at lower key-sizes. I am not advocating using smaller keys, just pointing out that there is more to brute-force resistance that simply just the key-length number. In general, this is a dumb trade to make, because more key bits are cheap and that computation costs every user. Things like what you describe exist-- where initial key scheduling does key stretching, etc. > Since memory intensity instead of pure computational intensity seems to be employed by some hashing alghorithms I wonder is that would be possible block ciphers as well. The way I understand this, it makes ASIC/FPGA brute-forcing a lot harder/expensive Anything is possible, but this often does more to hurt low-resource users than brute force also.
- mr__y 7y ago
  >but this often does more to hurt low-resource users than brute force also. 1MB memory usage would not hurt most of the low-resource users while having 1MB memory for each of the millions of computational units in a brute-force rig would hurt the attacker a lot more. I assume that it is relatively easy to have a huge number of brute-force cracking units in a simple GPU/FPGA/ASIC rig but if each of them would additionally need lets say 1MB of RAM that would present a serious problem for the constructor of such rig. I do get that AES will happily run on a 20-year old smart-card simplified cpu without a problem while my fictional 1meg-requiring cipher would be problematic, but then again it's 2019 and 1MB is not that of a problem for the least powerful smartphones or even embedded systems.
  - mlyle 7y ago
    > but then again it's 2019 and 1MB is not that of a problem for the least powerful smartphones or even embedded systems. 1MB means you basically obliterate caches and torture memory bandwidth every time you want to encrypt a tiny block. But ignoring that... Low cost microcontrollers with 4k or 8k of RAM total are still used in embedded systems and often have hardware AES built in. Even things like ESP32 are often considered relatively big and have 520k of ram. There are applications and services that have a million or more connected sockets with encryption at a time. This would represent a terabyte of RAM just for this 1MB block cipher scratchpad. If one were to just use a megabyte during key scheduling or something-- that's feasible, I guess, but it still locks out a lot of the embedded world.
    - vlovich123 7y ago
      True but also to remember that vendors build the chips the industry demands. So if they need to provide 1MB they will - it will just mean a larger BOM unless the chip package needs to grow. The size is going to be the biggest bottleneck there.
      - mlyle 7y ago
        You fixated on one bit of the argument, but if you want to discuss that: Memory on logic processes is expensive. That's why SRAM is precious on microcontrollers. Also, already the largest memory sizes require much larger than typical packages. A microcontroller with a few megabytes of RAM to support several crypto sessions with this cipher is going to be a big cost multiple over current micros.

by mr__y 7y ago

mlyle 7y ago

> you could imagine a cipher with a computational/memory[0] intensity so high that the brute force attack could be practically infeasible even at lower key-sizes. I am not advocating using smaller keys, just pointing out that there is more to brute-force resistance that simply just the key-length number. In general, this is a dumb trade to make, because more key bits are cheap and that computation costs every user. Things like what you describe exist-- where initial key scheduling does key stretching, etc. > Since memory intensity instead of pure computational intensity seems to be employed by some hashing alghorithms I wonder is that would be possible block ciphers as well. The way I understand this, it makes ASIC/FPGA brute-forcing a lot harder/expensive Anything is possible, but this often does more to hurt low-resource users than brute force also.

mr__y 7y ago
>but this often does more to hurt low-resource users than brute force also. 1MB memory usage would not hurt most of the low-resource users while having 1MB memory for each of the millions of computational units in a brute-force rig would hurt the attacker a lot more. I assume that it is relatively easy to have a huge number of brute-force cracking units in a simple GPU/FPGA/ASIC rig but if each of them would additionally need lets say 1MB of RAM that would present a serious problem for the constructor of such rig. I do get that AES will happily run on a 20-year old smart-card simplified cpu without a problem while my fictional 1meg-requiring cipher would be problematic, but then again it's 2019 and 1MB is not that of a problem for the least powerful smartphones or even embedded systems.
- mlyle 7y ago
  > but then again it's 2019 and 1MB is not that of a problem for the least powerful smartphones or even embedded systems. 1MB means you basically obliterate caches and torture memory bandwidth every time you want to encrypt a tiny block. But ignoring that... Low cost microcontrollers with 4k or 8k of RAM total are still used in embedded systems and often have hardware AES built in. Even things like ESP32 are often considered relatively big and have 520k of ram. There are applications and services that have a million or more connected sockets with encryption at a time. This would represent a terabyte of RAM just for this 1MB block cipher scratchpad. If one were to just use a megabyte during key scheduling or something-- that's feasible, I guess, but it still locks out a lot of the embedded world.
  - vlovich123 7y ago
    True but also to remember that vendors build the chips the industry demands. So if they need to provide 1MB they will - it will just mean a larger BOM unless the chip package needs to grow. The size is going to be the biggest bottleneck there.
    - mlyle 7y ago
      You fixated on one bit of the argument, but if you want to discuss that: Memory on logic processes is expensive. That's why SRAM is precious on microcontrollers. Also, already the largest memory sizes require much larger than typical packages. A microcontroller with a few megabytes of RAM to support several crypto sessions with this cipher is going to be a big cost multiple over current micros.