2

Many security algorithms today have such a large key length, that there's just no use in trying to brute-force a key. For example to find one AES-256 key you would have to try 2^255 keys on average.

My question is, if there's a special name for a brute-force attack where you would somehow know that a key "lies" in a specific range, which would reduce the amount of calculations so drastically that a brute-force attack suddenly becomes feasible.


An example about simple brute-force RSA-factorization might make it more clear:

We have a 2048-bit RSA key. Way too large to just try one number at a time to brute-force it.

But we assume now that I have a special algorithm that doesn't directly return one of the factors, but can tell us that one of the factors lies in a certain range k (plus / minus 1,000,000,000). Then we would only have to try the possibilities from k - 1,000,000,000 up to k + 1,000,000,000 and this is probably quite possible to brute-force.


No matter if such algorithms exist or not, is there a special name for this specific attack (reducing the possible key range to make a brute-force attack feasible)?

2
  • 3
    "to find one AES-256 key you would have to try 2^128 keys on average" - 2^255 actually, for average you divide keyspace by 2, and 2^256/2 = 2^255. Commented Jul 2, 2019 at 21:54
  • Pretty sure that would be called a weakness in one of the algorithms used or a vulnerability in one of the tools used to generate your key.
    – Ben
    Commented Jul 3, 2019 at 0:08

3 Answers 3

1

There is no term for this because this is not how cryptanalytic attacks work.

Typically, attacks like these do not reveal that a key lies in a specific range, but that the secret material has certain properties. Finding those properties is part of cryptanalysis in general. As such, I don't think there's a specific name for this since it really doesn't exist. Things that don't exist or are very rare don't always have specific names. You need a description. In this case, you would describe an attack that shows you that the secret material has certain properties.

Here's a simple example: Let's say I created a password hash by taking the integer representation of the password, modulo 256. The hash is thus an 8-bit integer in the range [0,255], which is obviously too little. But do we have to brute force all possible integers (infinity)? No. If we know that the hash is the number 163, we can tell that the input is congruent to 163 (mod 256). This is enough information to instantly generate a candidate password that hashes to the same result, but it doesn't tell you what the original password was unless there are very few possible passwords to choose from.

Obviously such an example is too simple for real cryptographic algorithms (although there are real checksum algorithms which use this technique). What does such an attack actually give you? A set of properties that an input must have for the attack to work. Sometimes the properties are easy to meet and require very little computation. Other times they have unknowns that must be filled by brute force or which are so complicated that finding them actually takes nearly as much time as a true brute force of the keyspace. A trivial example (in the cryptanalytic sense) would be for finding colliding MD4 inputs. Instead of giving you a flat range from a to b, you get something like:

MD4 collision properties

From the linked website:

It’s relatively easy to satisfy the first few constraints, but as you go on it becomes harder and harder because with each new constraint you have to ensure that you don’t mess up all of the prior ones. In our attack we satisfied all but 19 of Wang’s constraints and 1 out of the 2 additional constraints listed in the improved attack. This suggests that we need to generate 220 or around 1 million messages to find a collision. This seems to be borne out by experimental results.

I am not aware of any specific term that describes generating these 1 million messages other than, in this case, "MD4 collision attack". Note that this is not the best attack against MD4, and the best attacks have a complexity of less than 2. No, that's not a typo. It's 2, which is far less than 220. Attacks against better, modern cryptographic primitives which have a far higher complexity have even more complex conditions that must be met. Even MD5, which is considered fatally broken today, is far harder to break than MD4.

1

"Password Spray" is used to describe an attack in which a limited number of likely or easily guessed passwords are attempted against a number of accounts. It's usually used for on-line (e.g., try to log in) rather than off-line (e.g., get copies of hashes) attacks. To quote TheWindowsClub:

Password Spray Attack is quite the opposite of Brute Force Attack. In Brute Force attacks, hackers choose a vulnerable ID and enter passwords one after another hoping some password might let them in. Basically, Brute Force is many passwords applied to just one ID.

0

There's a subtype of attack where a given users past credentials, usernames, personal data can be used to narrow down the scope within which the brute force operates. Basically AI enriched brute force. Still brute force but with machine learning guiding it.

https://www.sciencemag.org/news/2017/09/artificial-intelligence-just-made-guessing-your-password-whole-lot-easier

This should explain it better than I can.

1
  • That's not a brute force attack though. It doesn't reduce input to a range.
    – forest
    Commented Jul 3, 2019 at 7:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .