Sorry to draw you in with this title, but you might as well finish reading it and see if you get something out of it. (If there are gains, please leave a comment in the comment section, if there are no gains, I will live eat ** next weekend, ha ha, this you also believe)
Supplementary note: wechat public number revision, the main impact on each number is quite big. At present from the background data point of view, the impact on me is not big, because I this anyway is a small, 😂 reading amount itself is little of the poor, the truth, 🐶 dog head (just from the communication group to learn the expression).
First go directly to the code:
boolean safeEqual(String a, String b) {
if(a.length() ! = b.length()) { return false;
}
int equal = 0;
for (int i = 0; i < a.length(); i++) { equal |= a.charAt(i) ^ b.charAt(i); } return equal == 0; } Copy the codeThe code above was translated from Scala to Java. The Scala version (the code that first attracted the attention of simstone) is as follows:
def safeEqual(a: String, b: String) = {
if(a.length ! = b.length) { false
} else {
var equal = 0
for (i <- Array.range(0, a.length)) { equal |= a(i) ^ b(i) } equal == 0 } } Copy the codeThis function is used to compare whether two strings are equal or not.
Look again at the back, moving head, slightly turning down can understand the doorway: by xor operation 1 ^ 1 = 0, 1 ^ 0 = 1, 0 ^ 0 = 0, to compare each, if every one is equal, two strings must be equal, finally stored accumulated variables or values surely equal to zero, or 1.
Think about it again?
for (i <- Array.range(0, a.length)) {
if(a(i) ^ b(i) ! =0) // or a(i) ! = b[i]
return false
}
Copy the codeWe talk a lot about performance tuning, and from an efficiency point of view, shouldn’t we be able to return two strings that are not equal as soon as we discover that one of them is different? (As shown above)
There must be…
Think about it a little more?
Combined with the method name safeEquals, you might learn something about security.
The code at the beginning of this article comes from playFrameWok, which is used to verify that the data in the cookie(session) is valid (including the validation of the signature), which is why Stone wrote this article.
I used to know how to improve efficiency by means of delayed calculation, but it is the first time that the results have been calculated but delayed return!
Let’s take a look at, in the JDK also has a similar approach, the following code excerpt from Java. The security. The MessageDigest:
public static boolean isEqual(byte[] digesta, byte[] digestb) {
if (digesta == digestb) return true;
if (digesta == null || digestb == null) {
return false;
}
if(digesta.length ! = digestb.length) { return false; } int result = 0; // time-constant comparison for (int i = 0; i < digesta.length; i++) { result |= digesta[i] ^ digestb[i]; } return result == 0; } Copy the codeAs you can see from the comments, the purpose is to compare in constant time complexity.
But what’s the risk that the time it takes is not constant? (Background music in my head: “Do you have a lot of question marks?” )
The truth
This is done to prevent Timing attacks. (Also translated as sequential attack)
Timing Attack
Timing Attack is a kind of side-channel Attack (or “side-channel Attack”, Side Channel Attack, referred to as SCA). Side-channel Attack is a kind of Attack that aims at software or hardware design defects and goes “wrong way”.
This attack is through power consumption, timing, electromagnetic leakage and other ways to achieve the purpose of breaking jie. Often surprisingly successful in many physically isolated environments, this new type of attack is far more effective than the traditional mathematical methods of cryptanalysis (according to one encyclopedia).
This method allows you to call safeEquals(“abcdefghijklmn”, “XBCdefghijklmn “) (only the first digits are different) and safeEquals(“abcdefghijklmn”, “Abcdefghijklmn “) (two identical strings) takes the same time. Prevents violent breaking of the string to be compared by changing the input a lot and counting the runtime.
For example, 🌰, if implemented in the “efficient” manner described earlier. If a user sets the password as password, p0000000 will run longer than any other string from a to Z by enumerating the first digits from a to Z (which may be much wider). In this way, we can guess that the first user password is likely to be P, and then continue to iterate one by one and finally pojie out of the user’s password.
Of course, the above is from a theoretical point of view, it is really easy to understand. But in fact, it doesn’t always feel right to count the elapsed time, which is too sensitive to the environment, such as network, memory, CPU load and so on.
But security issues feel more like “trust something than nothing.” In order to prevent timing attacks (especially those related to signature/password authentication), all major languages provide corresponding security comparison functions. Various software systems (such as OpenSSL) and frameworks (such as Play) are implemented in this way.
For example, “The best programming language in the world” (with few followers, the comments section should not be a fight) — in PHP:
// Compares two strings using the same time whether they're equal or not.
// This function should be used to mitigate timing attacks;
// for instance, when testing crypt() password hashes.
bool hash_equals ( string $known_string , string $user_string )
//This function is safe against timing attacks. boolean password_verify ( string $password , string $hash ) Copy the codeActually all language version of the implementation and the version is the same as the above, remove every two strings to xor (^) and or (|), finally, whether the result is 0 to determine whether two strings are equal.
If safeEquals is not implemented at first, subsequent releases will patch to fix such vulnerabilities.
For example, Release Notes[1] in JDK 1.6.0_17 mentioned fixing the bug in MessageDigest. IsEqual, as shown in the figure below:
The openJDK bug fix diff[2] is:
Does Timing Attack really work?
I think the API of every major language uses this kind of implementation, must be reasonable, should be able to be used in theory. This paper claims to have broken OpenSSL 0.9.7 RSA encryption using this timing attack method. For an introduction to the RSA algorithm, see this article I wrote earlier.
Remote Timing Attacks are Practical[3] Remote Timing Attacks are Practical[3]
Timing attacks are used to attack weak computing devices, such as smart cards. We’ve found through experiments that it can also be used to attack ordinary software systems. In this paper, experiments prove that this timing attack can break the private key of an OpenSSL-based Web server. The results show that timing attack is feasible for network attack in practice, so major security systems need to resist this risk.
Finally, AFTER all, I am not specialized in the complete direction, the above description is based on my understanding, if there is any wrong place, please leave a message to point out. Thank you
Supplementary note 2: Thank you for reading the article, so THAT I still have the motivation to continue to update the original.
I do not publish many articles, but I hope to write articles to achieve the purpose is: take up your reading time, as far as possible to let you gain.
If you think my article is helpful, please help to forward and share. In addition, please don’t forget to click on the upper right corner of the official account to add a star, so that you don’t miss the follow-up wonderful article (wechat has been revised, maybe I can not push the article to you).
Original is really not easy, I hope you can help me a small favor, if the content of this article you feel inspired, harvest, please help to click “watching”, or forward to share so that more partners see. References:
- Timing Attacks on RSA: Revealing Your Secrets through the Fourth Dimension
- Remote Timing Attacks are Practical
The resources
[1]
Release Notes: http://www.oracle.com/technetwork/java/javase/6u17-141447.html
[2]
The bug fix its diff: http://hg.openjdk.java.net/jdk6/jdk6/jdk/rev/562da0baf70b
[3]
Remote Timing Attacks are Practical: http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf