Summary of antecedents

As we will continue to update the iOS application security series of articles, here are a few more cryptography, application signature, for the subsequent expansion of code injection, assembly, shell cracking and other articles to lay a foundation.

cryptography

Overview of cryptography

Cryptography is the technical science of creating and breaking codes. The study of the objective law of cryptography changes, which is applied to the preparation of cryptography to protect the secret of communication, is called cryptography; The application of cracking codes to obtain communication information is called cryptography.

The origins of cryptography date back to 2000 years ago. Today’s cryptography is based on mathematics.

Cryptography tracing

The history of cryptography can be traced back roughly 2,000 years to the legend that Julius Caesar sent messages in code to prevent enemy interception. What Caesar did was simply to create a table of correspondence for the two dozen Roman letters. In this way, if you do not know the password book, even if the interception of a message can not understand.

Important nodes:

  • in1976Until 2000, all encryption methods were based on the same pattern: encryption and decryption used the same algorithm. When exchanging data, the two parties communicating with each other must tell each other the rules, otherwise it cannot be decrypted. Then the encryption and decryption rules (referred to as the key), it is particularly important to protect. Passing the key becomes the biggest problem. This encryption method is calledSymmetric encryption algorithm(symmetric encryption algorithm)
  • 1976Two American computer scientists, Diffie (W.Diffie), Herman (M.Hellman) proposed a new idea, which can complete the key exchange without directly transferring the key. This is called”Diffie Hermann key exchange“Algorithm. It opened a new direction of cryptography research.
  • 1977Ronald Livest, three mathematicians at the Massachusetts Institute of Technology (Ron Rivest), Adi Samore (Adi Shamir) and Leonard Aardman (Leonard Adleman) together designed an algorithm that could implement asymmetric encryption. The algorithm, named after the three of them, is calledRSAAlgorithm.

RSA Encryption Algorithm

RSA

An encryption algorithm developed in the 1970s. The encryption mode is special and requires two keys: publickey and privatekey. Public key encryption, private key decryption; Encrypt the private key and decrypt the public key. This encryption algorithm is the great RSA.

The algorithm is so reliable that the longer the key, the harder it is to crack. According to the published literature, the longest RSA key ever cracked is 768 bits. That is, a key longer than 768 bits is unbreakable (at least, no one has announced it publicly). Therefore, the 1024-bit RSA key is basically secure, and the 2048-bit RSA key is extremely secure.

(Of course, the drawbacks of RSA are easy to think of: relatively low efficiency, limited byte length, etc. So in practice we tend to use symmetric encryption together, using RSA for key content.)

Mathematical principles of RSA

Understand the content of this section

1. Discrete logarithm problem

Q: what power of three is modulo 17 equal to 12?

  • Obviously, for the discrete logarithm problem, it’s easy to compute forward to get 12 on the right-hand side. But when you do it backwards, you don’t know where to start. You have to do everything.

  • And when the modulus uses the prime number 17, the result is fixed between 1 and 17. When the module 17 is large enough, even if we know the algorithm, we also know the prime number 17 and the answer. If we want to calculate the question mark value in the figure above, we can imagine how difficult it is and how much calculation is required.

2. Euler function φ

Euler function:

Given any positive integer n, the number of positive integers less than or equal to n that can form a reciprocal relationship with n.Copy the code

The way to compute this value is called the Euler function, denoted by: φ(n)

  • Ex 🌰 :

φ(8) has 1,3,5,7 = φ(8) = 4

φ(7) has 1,2,3,4,5,6 = φ(8) = 6

  • Q:

So what is φ(56)?

So before we start counting them all, let’s look at the characteristics of euler functions.

  1. whennWhen it’s prime,Phi (n) = n - 1
  2. whennCan be decomposed into the product of two mutually essential integers, asn = A*BIs:Phi (A * B) = phi phi (A) * (B)

Therefore:

ifNIt’s two prime numbersP1 和 P2Is the product ofφ(N) = φ(P1) * φ(P2) = (P1-1)*(P2-1)

So obviously φ(56) = φ(7) * φ(8) = 4 * 6 = 24

While φ(63) = φ(7) * φ(9) = (7-1) * (9-1) = 48

Euler’s theorem

If two positive integers m and n are mutually prime, then m to the φ(n) minus 1 is divisible by n.

Tip: We don’t need to prove the theorem, just remember it.

3.1 Fermat’s Little Theorem

Fermat’s little theorem is based on Euler’s theorem, and when n is prime (φ(n) the result is n-1.)

So:

If two positive integers m and n are mutually prime, and n is prime, then m to the n-1 minus 1 is divisible by n.

4. Formula conversion

  • First of all, according to Euler’s theorem
  • Due to the1 的 kTheta to the power is equal to theta1, then

  • Due to the≡ 1 * m m, then

  • Before moving on to the fourth installment, we’ll mention one concept: modular antielements

If two positive integers e and x are mutually prime, then the integer D must be found such that Ed -1 is divisible by x. So d is the inverse of e with respect to x.

Then the formula is:

  • Let me switch over

Notice the red box in step 5 and step 3. That is, when x is equal to phi (n) :

Φ (n)

Note: In the first step of formula derivation, the premise of Euler’s theorem is that M and N are mutually prime. However, due to the relation of modular inverse elements, the above results are still valid as long as m < n is satisfied.

The main part of the show is to use the actual scene to see the Process of Diffi Hermann key exchange

Principle:

Therefore:

(where d is the modulo inverse element of e with respect to φ(n), since x = φ(n), then similarly, e and φ(n) are mutually prime.)

For example: m = 3, n = 15, φ(n) = 8, e = 3, d = 11.

Here, we will get the principle of RSA algorithm. So let’s introduce the corresponding

Principle of RSA algorithm

  • 1. N can be very large, typically 1024 bits long. (The largest integer that humans have decomposed so far, 232 decimal bits, 768 binary bits)

  • 2, because of the need to find φ(n), so according to the characteristics of the European function, the simplest way n by multiplying two prime numbers: prime numbers: P1, P2. So phi of n is equal to p1-1 times p2-1.

  • Finally, e and D are obtained from φ(n). A total of six numbers are generated: P1, P2, n, φ(n), e, and D

    • Among themn 和 eCompose a public key.
    • n 和 dForm a private key.
    • mTo clear.
    • cFor the cipher.

(Except for the public key, which uses n and e, the other four numbers are not public.)

The HASH algorithm

Introduce the HASH

A Hash is a Hash algorithm that transforms an input of arbitrary length into an output of fixed length, which is the Hash value. This transformation is a compression mapping, that is, the space of hash values is usually much smaller than the space of input, and different inputs may be hashed into the same output, so it is impossible to determine a unique input value from the hash value. Simply put, it is a function that compresses a message of any length into a message digest of a fixed length

Characteristics of the HASH

  • The algorithm is public
  • The same data, you get the same answer
  • To perform operations on different data, e.gMD5The default result is zero128position32A character (16Base identifier)
  • You can’t invert this thingHASHNot used for encryption and decryption)
  • Summary of information, information “fingerprint”, is used to do data identification

Main Uses of HASH

  • Encryption of user passwords

  • Search engines (matching search content based on hash values, etc.)

  • copyright

  • A digital signature

  • Cloud disk file audit/identification of the same file

  • . , etc.

HASH Security Discussion

Since the same data hash results are the same, so the existence of a large number of trillion-level hash result record databases in the market, this irreversible algorithm has also become a unique existence of decryption.

Therefore, we often use the following operations:

  1. Add salt (common practice in early days)
  2. Nested hash
  3. Dynamic salt
  4. HMAC (or dynamic salt)
  5. . , etc.

HMAC encryption scheme

HMAC is encrypted with a single key that is hashed twice. In real development, the key is usually sent from the server to the client and may be bound by account. In addition, you need to set the registration and login logic based on actual service requirements (such as new device authorization to determine whether the server can deliver the key to the client).

See this maybe you have the same question as me.

doubt

I don’t care how you nest salt HMAC or whatever you do with passwords. Since you’re logged in with an account and an encrypted password. I can directly call the interface to log in.

Yeah, that would be GG, wouldn’t it?

This involves the problem of interface security. There are many processing methods, such as using HTTPS for all requests and using the combination of symmetric encryption and asymmetric encryption to encrypt data.

Of course, even the most secure encryption algorithm has the risk of being cracked. Therefore, the following way, we can understand the reference, it can be more effective to solve the packet capture problem:

answer

    1. The time of registration
    • Use the sameHMACWhen registered, the client passes the user name to the server.
    • The server randomly generates a key and returns it to the client and binds the key to the user in the user table.
    • The client gets thiskeyEnter the user password in plain textHMACThe hashes are sent to the server for saving.
    1. login
    • Log in to the userHMACAfter thehashValue plus a timestamp accurate to the minute (The time is uniformly distributed to the server. I believe that all projects are using the server time.) and hash.
    • The server receives the request and validates the current time and the previous minute time respectively plus the previously stored timeHMACAfter password is carried outhash. If the login succeeds once, the login succeeds.

Think about:

Why can the preceding methods effectively prevent packets captured on the interface?

  1. The userHMACAfter thehashThe value is transferred only once when the account is registered.
  2. Catch the timestamp plus in the interfaceHMACAfter thehashHashing values is hard to guess how to nest.
  3. Use the source data in the captured interface (timestamp plusHMACAfter thehashThe validity period is 1 minute 59 seconds at most and 1 minute at least (the validity period can be flexibly controlled). That is to say, after capturing the source data, the packet capture personnel must log in within two minutes; otherwise, the packet will be invalid.

HASH digression

There may be partners who have encountered the situation of uploading cloud disk files are harmonious, and changed the name or suffix to re-upload or not. That’s one way to use a HASH. Understand that a HASH is a HASH of binary data. So change the name and suffix of the file binary will not change.

But compression is possible.

base64