Check if two anonymously signed messages have the same author I need digital signature scheme with following rules:

Signature is "anonymous" which means it doesn't expose author identity (See papers in this answer. Anonymous RSA version or Boneh-Boyen algorithm satisfy this clause).
Author can create some anonymous signed message and then create another anonymous signed messages "related" to any previous signed message.
"Relation" means third party can make sure this second message have same author as its "related message".

For example:

Alice write message and sign it. For example it is volume of the book. Bob cannot determine this message belong to Alice even he has Alice's public key.
Alice write another message, which are for example second volume of her book and sign it. Bob also cannot determine this message belongs to Alice, but he can make sure this message have same author.
Alice write third message and sign it. This message is not related to previous, so Bob cannot determine nor author neither relationship with previous messages.

Ok, here's a simple method that appears to address your requirements.

It uses two signature methods; the first one (the "inner signature") is conventional; the second one (the "outer signature") is anonymized.

When Alice generates a message $m$, she either generates a public/private key pair $Pub_a, Priv_a$ for the inner one, or reuses a $Pub_a, Priv_a$ pair that she previously generated.  She then signs the message with the private key, generating $Sig_a(m)$, and forms the tuple $(Pub_a, Sig_a(m))$.  When then interacts with server to anonymously generate the public signature of this tuple $Sig_s(Pub_a, Sig_a(m))$, and generate as a signature the tuple:

$$Sig_s(Pub_a, Sig_a(m)), Pub_a, Sig_a(m)$$

To validate this signature, one would verify that $Sig_s(Pub_a, Sig_a(m))$ is a valid signature for $Pub_a, Sig_a(m)$ (based on the Server's public key), and if $Sig_a(m)$ is a valid signature of the message (based on the public key $Pub_a$).

As for your requirements:

It is anonymous; $Pub_a$ is a random public key, and so there's nothing to link it with Alice
It is linkable; Alice can use the same $Pub_a, Priv_a$ to sign two related messages; anyone can see that those two signatures use the same $Pub_a$ value (and hence must be signed by the same person)
Links are trustable; as no one else knows the value $Priv_a$, no one other than Alice can sign a message using $Pub_a$


Is it safe to use unauthenticated AES CBC when encrypting random bytes? I am studying an application with an AES crypto implementation that works that like the following:

PBKDF2 is used with X iterations and SHA-256 to generate a 256-bit "master key" from a user-provided password and salt.

master_key = pbkdf2(
    password,
    salt,
    iterations,
    alg: SHA256,
    size: 32)

A crytpo-safe RNG is used to generate 512 bits of "key material" .

key_material = random_bytes(
    size: 64)

The key material is then encrypted with the 256-bit master key, unauthenticated.

encrypted_key_material = encrypt_aes(
    data: key_material,
    key: master_key,
    hmac_key: null,
    mode: CBC)

The encrypted key material is persisted on the device for later encryption use. The application user only needs to provide the PBKDF2 generated master key to decrypt it.

It should be noted that the encrypt_aes function generates and uses a standard 16 byte random IV with every operation which is part of the returned encrypted bytes (along with the computed encrypt-then-mac HMAC data).
When the application needs to encrypt some data, half of the key material is used as the encryption key and the other half is used as the HMAC key.

key_material = decrypt_aes(
    data: encrypted_key_material,
    key: master_key,
    hmac_key: null,
    mode: CBC)

encryption_key = key_material.split(0, 31)
hmac_key = key_material.split(32, 64)

And now encryption of other data can be performed in the application, which is authenticated.

encrypted_data = encrypt_aes(
    data: "Hello World",
    key: encryption_key,
    hmac_key: hmac_key,
    mode: CBC)

decrypted_data = decrypt_aes(
    data: encrypted_data,
    key: encryption_key,
    hmac_key: hmac_key,
    mode: CBC)

// decrypted_data is now "Hello World"

I understand that CBC mode should always use HMAC authentication to protect against oracle attack vectors. As we can see here, an HMAC is used for encrypting data in the application (step 5), but it is not used when encrypting the random key material (step 3 and 4) that gives access to all of that data. This is presumably this way because PBKDF2-SHA256 does not produce enough bits to supply a 256-bit HMAC key for protecting the key material (step 3), hence why 512 bits of key material is derived separately for further encryption operations.

Is this a safe implementation? Does the fact that the key material is random byte data change its need to have HMAC authentication to protect it from attacks? Is the key material decryption from step 4 subject to the same attack vectors as standard string decryption, as in step 5?

Is this a safe implementation?

No. An adversary can change just the first encrypted block that contains part of the AES data key. Then HMAC authentication will succeed, but decryption with the AES key will result in the wrong plaintext message. If an IV is used then the IV can also be changed, resulting in only the first 128 bits of the AES data key to be changed.

After all, CBC has limited error propagation, and the block size of AES requires a minimum of 4 blocks to encrypt two 256 bit keys.

If padding is used then padding errors may also result in a padding oracle attack on the key material. But those would only work in a limited amount of scenarios.

  Does the fact that the key material is random byte data change its need to have HMAC authentication to protect it from attacks?

No, not necessarily. It depends on how the random data is used. If alteration of the random data can help with creating an active attack then integrity / authenticity is required. To state that it doesn't need protection just because it is random data is certainly wrong.

  Is the key material decryption from step 4 subject to the same attack vectors as standard string decryption, as in step 5?

No. The bits of the encrypted random data are unrelated to each other and they do not need to be padded, which thwarts many attacks on CBC mode. But it still has limited error propagation and no integrity / authenticity.

PBKDF2 should indeed be limited to generate only as many bits as the internal hash function provides. Generally you'd use an additional Key Based Key Derivation Function or KBKDF such as HKDF to derive the keys from a master secret, generated by PBKDF2:

$$K_{master} = \text{PBKDF2}(p, ...)$$
$$K_{enc} = \text{HKDF}(K_{master}, \text{"enc"})$$
$$K_{mac} = \text{HKDF}(K_{master}, \text{"mac"})$$

This doesn't require any additional storage as the labels "enc" and "mac" are simply constant values.

An ugly hack would be to also include the IV (if present) and ciphertext of the encrypted keys in the HMAC verification. I'm just mentioning this because the protocol may have used this already - it could be just a change of an offset - and it may have been overlooked.


Brute Force Attack Strategies A Brute Force Attack obviously involves attempting to decrypt ciphertext (with the associated  plaintext being known) using all possible encryption keys.

Aside from attempting all possible encryption keys in sequence, have there been, or is there any alternative methods of performing a brute-force attack?

I'm aware of the Distributed.NET attack on DES (which leveraged parallel/distributed computing)  whereby the entire keyspace of DES was subdivided and allocated to a number of different computers, with each computer decrypting a piece of ciphertext using the section of the keyspace it was allocated.

No, you can divide and distribute, but if you do anything else (such as filtering for candidates) then it would not officially be a brute force attack anymore. You will have to iterate over the full key space one way or another.

With DES I guess it is acceptable to forget about parity while iterating over the key space, only effective key bits have to be traversed.

Finally, there may be specific methods required to filter out possible candidates if it isn't a known plaintext attack (which is however assumed in the question).


TLS1.3 encrypted handshake I read that TLS 1.3 supports encrypted handshake. Is it achieved using encrypted_extensions?

Does it mean that the records which contains handshake messages are encrypted/protected from the point of view of record-protocol?

Or

Does it mean that the handshake protocol itself encrypts its message payload and records are plain text from record-protocol perspective?

In TLS 1.3, all messages after ServerHello are encrypted. This encryption happens before EncryptedExtensions is sent. The traffic keys protect the record layer payload; they transform TLSPlaintext structs into TLSCiphertext structs.

During the handshake, the following messages are transmitted:

Client $\rightarrow$ Server: ClientHello (generate client nonce)
Client $\rightarrow$ Server: ClientKeyShare (generate ephemeral Diffie-Hellman parameter $X = g^x$)
Server $\rightarrow$ Client: ServerHello (generate server nonce)
Server $\rightarrow$ Client: ServerKeyShare (generate ephemeral Diffie-Hellman parameter $Y = g^y$)

At this point, both Client and Server can calculate the pre-master secret $g^{xy}$, and this is part of what goes into a PRF to derive a handshake master secret (HMS). Then you derive a handshake secret traffic key $t_{hs}$, which depends on HMS and the nonces.

The EncryptedExtensions message is the first one sent after $t_{hs}$ is generated. This and the rest of the handshake messages (like ClientCertificateVerify, ServerFinshed, etc.) are encrypted with $t_{hs}$. See how the keys are computed here.

You can see sample handshake traces here. (Since TLS 1.3 is still in draft form, this will be obsoleted soon.)


Advantages of 64-bit CPU smartphone Advantages of having a 64-bit CPU vs 32-Bit CPU smartphone
  …
  3. Complex Encryption. Improved Security: 64-Bit can process incredibly large numbers allowing you to better encrypt data against unauthorized access.

source: http://www.amongtech.com/what-is-the-advantage-of-having-a-64-bit-smartphone/

Is the above statement correct, in particular with regards to the term “complex encryption”? I mean, how is the complexity increased with 64 bits? Is that related to the increase of the key size?

In terms of marketing hype, that statement rates about a 9 in a scale from 0-10.

The reason is that we don't choose the encryption algorithm based on how many bits the CPU can handle at once.  Instead, we choose a secure algorithm, and then implement it using the resources that the CPU provides us.  There aren't any algorithms we cannot implement on a 32 bit CPU; hence a 64 bit CPU does not allow us to use new ones.

Now, there is a tiny kernel of truth there (and so doesn't rate a perfect 10 on the scale); sometimes a 64 bit CPU allows us to implement an algorithm more efficiently than a 32 bit CPU.  However, the delta is usually not large enough to influence an 'can-we-encrypt' decision.


Public key on Server Key Exchange Generation vs Public key on Server's Certificate To understand the distinction between TLS 1.2 and TLS 1.3. I am stuck in the past understanding for TLS and the current reference I am studying:

As I know certificate goes with owner's public key, and its public key is used for key exchange between client and server to generate long-term pre-shared key.

But I feel confused with this understanding when I look into the phase Server Key Exchange Generation in TLS 1.2.

It says public key derived from server for key exchange is not the attached one but the new one derived from random number $2^{256} -1$ as private key.

Which one is right? I have heard about both in different references.
Also it makes me breed another question about prevention from man-in-middle-attack via certificate as follows:

If a user's browser is tampered with spoofed DNS resolver which returns fake server's IP address that serves same host name of website with the certificate fetched from real website. How the browser verifies the integrity if the TLS handshake uses two different key pairs in certificate verification and key exchange?

TLS ≤1.2 allows different types of handshakes where the key exchange and the authentication rely on different mechanisms. The type of handshake is determined by the choice of cipher suite. The page you link to illustrates the most common type, where key exchange and server authentication work independently. This type of handshake is the one used by ciphersuites with ECDHE or DHE in their name.

For this type of handshake, the key exchange uses an [elliptic curve] Diffie-Hellman key agreement algorithm with an ephemeral (i.e. single-use) key. To generate the ServerKeyExchange message, the server generates an (EC)DH private key, and the ServerKeyExchange message contains the corresponding public key. The client does the same for the ClientKeyExchange message. The two sides then perform a Diffie-Hellman key agreement algorithm using their own private key and the other side's public key to generate a shared secret. By the design of DH, the two sides generate the same shared secret. This shared secret is the premaster secret for the TLS protocol.

In the specific example in your link, the server chose the X25519 group for the key agreement. For this particular group, a private key is an integer between $0$ and $2^{256}-1$.

None of this allows the client to know who it's exchanged data with. This comes from a different part of the ServerKeyExchange message: the signature. The server sends a signature of the important handshake data so far made with its private key. Specifically, the signed data includes the client nonce from the ClientHello message, the server nonce from the ServerHello message, and the DH public key. Previously, the server sent a Certificate message containing its certificate. The client verifies that:

The signature sent by the server is a correct signature of the appropriate handshake messages, made with the private key corresponding to the public key in the certificate sent by the server.
The certificate is signed by a certificate authority (CA) that the client trusts, or more generally that there is a chain of trust going from a trusted CA to the server's certificate.
The subject name in the certificate matches the server name that the client was attempting to contact.

A man-in-the-middle attacker who spoofs DNS records won't be able to get all of these verifications to pass.

The attacker can send the expected certificate and replay a good signature from a past exchange that it observed with the legitimate server, but then this signature won't be correct, because the handshake messages include a random nonce sent by the client.
The attacker can forward the ClientHello message to the legitimate server, get the legitimate server's ServerExchangeMessage and forward that to the client. Since the signature in that message includes the DH public key chosen by the server, the attacker won't have a way to find the shared secret. In this case, the exchange can go through if the attacker keeps forwarding both sides' messages intact, but the attacker won't be able to decrypt the messages or to modify them undetected. Since the attacker isn't able to violate the expected security properties of the TLS protocol, they aren't actually attacking anything: they're just a TCP router.
The attacker can send the expected certificate and a signature made with its own private key, but then the signature won't be correct, because the attacker would need the legitimate server's private key to make a correct signature.
The attacker can send a certificate containing fake data, but then the client will detect that the certificate is not internally consistent or that the certificate is not signed by a CA that it trusts.
The attacker can send a valid certificate made by a CA that the client trusts, but then (assuming the CA has done its job correctly) this certificate will contain a subject name that the attacker owns, and not the subject name that the client was trying to contact.


How can a user-input password be used to generate a natural-like dictionary corpus? I'm curious about the implications of cryptography and the generation of natural text (i.e using Markov chains), and I am wondering if there has been any cryptographic protocols that involved generating a document key with legible English-language words from a user-supplied password (maybe hashed, or went through some one-way function). For example:

E(sha256(password)) = DocumentKey

If not, is there any proposed way of accomplishing something like this?

If I had such problem, I would operate as follows:

Obtain a list of 8192 different words. Then the $x$-th word of this list is denoted by L[x] (where $x$ is a natural number in decimal).
Given any bitstring (hash of the password), split it into 13-bit parts. Denote an $i$-th part by N_i.
The sequence of words is L[N_1] L[N_2] L[N_3] ....

For example, SHA3-512 online web app shows that SHA-3-512("MyPassword") starts with the following bytes:

35 c6 36 f4 40 b7 d7 40 7a ...

Converting this hash to a binary form (byte after byte) and splitting into 13-bit parts yields the sequence

0011010111000 1100011011011 1101000100000 ...

Converting each part from binary to decimal yields

L[1720] L[6363] L[6688] ...

If the list is taken from Wiktionary:Frequency_lists/PG/2006/04/1-10000, the resulting sequence of English words would be

admit billion lists ...

if we assume that 13 zero bits correspond to the last word of the list. If we assume that 13 zero bits correspond to the first word of the list and 13 set bits correspond to the last word of the list, then the resulting sequence of English words would be

supply shorter gallop ...


Long or short encryptions? Is it generally considered desirable - or not? - to use an algorithm which encrypts a single byte into a byte array of length around 5 or 10?  Greater length allows me to add additional layers of obfuscation, but I don't know whether this is considered the sign of a naive amateur (which I am).

There is no security improvement for using an algorithm with ciphertext expansion. In fact, it's really only an unavoidable side-effect of certain public key operations. It's not something that's desired.
Anyway, time for the obligatory don't roll your own. No matter how secure you think it is, it isn't. If you want to learn about cipher design, read about existing ciphers, like this one.


Ciphertext indistinguishability (IND-CPA) for symmetric cryptography My understanding are these steps are necessary for symmetric cryptography to be IND-CPA:

The adversary submits two distinct $M_0$, $M_1$ plain-texts to the challenger.
The challenger selects one of them at random and encrypts it with the symmetric key and gives cipher-text C.
The adversary has to guess which message was encrypted based on C with a probability greater than 1/2 for the cipher-text to be distinguishable.

If the adversary wants to play the game again can he do $M_0$ and $M_2$? Or do they have to be new plain-texts?

Also I have an encryption algorithm that I am trying to apply IND-CPA test on it. How do I go about finding the probability mathematically, any hints or steps should I take?

First off, your definition is not IND-CPA: In the IND-CPA setting, the adversary has access to an encryption oracle. As you have already determined, no deterministic encryption scheme can be IND-CPA secure. I don't think IND-CPA is widely used for symmetric encryption though (although I might be wrong), semantic security might be a better option. For public key schemes, this is the same thing, but for symmetric schemes, it is not.

Semantic security informally says that you can't derive any information from a ciphertext about the underlying plaintext. Formally (from Katz and Lindell: Introduction to Modern Cryptography):

A private-key encryption scheme is semantically secure if for every PPT (= probabilitsitc polynomial-time) algorithm $\mathcal A$ there exists a PPT algorithm $\mathcal A'$ such that for all efficiently sampleable distributions $X = (X_1, \dots)$ and for all polynomial-time computeable functions $f$ and $h$, there exists a negligible function $negl$ such that $\vert Pr[\mathcal A (1^n, Enc(k, m), h(m)) = f(m)] - Pr[\mathcal A'(1^n, h(m)) = f(m)]\vert \leq negl(n)$,
where $m$ is chosen according to distribution $X_n$  and the probabilities are taken over the choice of $m$ and the key $k$, and any random coins used by $\mathcal A$, $\mathcal A'$ and the encryption process.

If you look closely, you see that $\mathcal A$ has access to an encryption of $m$ where $\mathcal A'$ does not. The requirement is that this gives $\mathcal A$ no advantage, because for any function $f(m)$, the two do just as well.

Unfortunately, proving this kind of security is rather ugly, which is why (in public key cryptography, where both are the same) the IND-CPA notion is usually used. How to prove security for your scheme depends on your scheme, without further details, it will be hard for anyone to help you with that. The approach is generally to show something along the lines of "If an adversary $\mathcal A$ can break my system, I can construct an algorithm $\mathcal B$ (which calls up $\mathcal A$) that breaks problem $X$, but problem $X$ is considered hard". For example, ElGamal reduces to the decisional Diffie-Hellman problem this way, which is related to (and a stronger assumption than) the Discrete Log problem.


Why sorting is needed for Meet-in-the-middle attack The weakness of double DES, E (k1, E(k2, M)) is that Meet-in-the-middle attack is possible. When performing Meet-in-the-middle attack, we first need to build the table with the first column all the possible keys and the second column all the encryption with these keys, then second step is sorting the second column, why do we need to sort the second column? What do we base on when performing the sorting?

That's an optimization for the attack. It would work without it, but slower.

To do a Meet-in-the-middle attack, we need to encrypt a known plaintext with every possible key and save the resulting text (with the used key) in a list. Now we decrypt a known ciphertext with every possible key and look if we got the resulting text in our list.

We want to know the key for a specific ciphertext. Searching for a specific value in an unordered list is quite hard: We need to look at every single entry and see if it is what we search. That takes (on average) $\frac{n}{2}$ attempts (with $n$ = the key space of the algorithm, for DES it is $2^{56}$).

If we sort the resulting list before we do the decryption we can use the Binary Search. This reduces the search attempts to ca. $\log_2(n)$ (n = the keyspace). That's only 56 for DES, much less than with an unsorted list.

Small note: We sort the column with the key at the same time as we sort the column with the ciphertext. For example, the first key will be the key for the first ciphertext.


Could a strong round function be immune to slide attacks An excerpt from the wikipedia article on slide attacks states:

  ...The only requirements for a slide attack to work on a cipher is that it can be broken down into multiple rounds of an identical F function. This probably means that it has a cyclic key schedule. The F function must be vulnerable to a known-plaintext attack...

and:

  ...Once a slid pair is identified, the cipher is broken because of the vulnerability to known-plaintext attacks. The key can easily be extracted from this pairing....

The statements:

  The next step is to collect 2^{n/2} plaintext-ciphertext pairs. Depending on the characteristics of the cipher fewer may suffice, but by the birthday paradox no more than 2^{n/2} should be needed.

lead me to think that even a truly random oracle would produce slid pairs, so it would appear that eliminating the existence of slid pairs is not a possibility.

My question is relatively simple. Suppose the round function of a cipher was resistant to known plaintext attack (i.e. known plaintext does not facilitate recovery of key information). Could such a cipher claim provable resistance to slide attacks? If not, what advantage would a slid pair offer an attacker?

Wikipedia is correct: any cipher that consists of a repeated number $n$ of iterations of the same function $F$ is vulnerable to the slide attack. Once you find a slid pair, the security of the cipher degrades to the security of $F$.

Generally speaking, 1 application of $F$ is not enough to withstand standard attack methods (e.g., differential, linear, etc). When you have a slid pair $(x, F^n(x)), (F(x), F^{n+1}(x))$ you can, for example, attack $x$ and $F(x)$ directly, thus recovering the key. What you can do precisely with a slide attack is specific to the cipher in question, however.

Note that if $F$ itself is ideal, then the slide attack is not effective. But in that case iterating $F$ is pointless, since you can use $F$ directly at $n$ times the speed!

There are two simple ways to prevent slide attacks:

Make your block size large enough. If your cipher has a 256-bit block, it will take (in the optimal case) $2^{128}$ plaintext-ciphertext pairs to get a slid pair, in which case it doesn't really matter whether slide attacks apply or not.
Make each round different. This doesn't need to be a large modification; for example, the Keccak permutation simply xors a different constant (the $\iota$ function) into the state at the end of each round, and this suffices to eliminate slide attacks.


What are some different cryptography methods? Some of the most effective cryptography methods and algorithms are based of factoring large prime numbers (e.g. RSA). I'm curious whether there are some other cryptography methods. Somethings that is very mathematical or physical based. Of course, I know about quantum cryptography, but I'm interested in other things also. For example, braid groups which have connection to knot theory can have application in cryptography. What I am asking is for a similar thing. I mean, is there any branch or equations in mathematics or physics that can lead to a cryptography methods.

All mathematical groups can be used to perform an ElGamal encryption, so that is a first kind of math. That's where elliptic curves are useful: they have a group structure. If you find a group, you can build a cryptosystem out of it. However, as @poncho pointed out, different groups have different properties with regards to security. For instance, elliptic curves are better than modular groups because they do not have a specific structure which can be leveraged to solve the discrete logarithm problem (see http://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm for an example of algorithm working only in modular groups).

You also have cryptosystems based on lattice related problems. In particular, lattices have been used to create the first fully homomorphic cryptosystem (see the references in http://en.wikipedia.org/wiki/Homomorphic_encryption).

A system which turned out to be very bad was built from the knap sack problem (see the Naccache–Stern knapsack cryptosystem on wikipedia).

For symmetric crypto, the theory of boolean functions can explain how the functions inside Feistel Networks or substitution permutation network are chosen. This yields connexions with coding theory and of course with finite fields of size $2^n$.


How does future secrecy fail for Signal group messaging? In the paper More is Less: On the End-to-End Security of Group Chats in
Signal, WhatsApp, and Threema, the abstract claims that

  We additionally show that strong security properties, such
  as  Future  Secrecy  which  is  a  core  part  of  the  one-to-one
  communication in the Signal protocol, do not hold for its group
  communication.

Failure of future secrecy makes sense for Whatsapp and Threema, since Threema uses a static key and Whatsapp uses a single symmetric key ratchet for group messaging, both of which are vulnerable to session state compromise. However, the paper states that Signal uses a normal double ratcheting scheme for group messaging such that group messages are indistinguishable from pairwise messages.

How does future secrecy fail for group messaging when the session state is refreshed whenever the keys are ratcheted?

Note: It seems that future secrecy fails due to the ability to join a group just by knowing its GroupID. Assuming that group update messages are properly authenticated, does future secrecy still fail for Signal's group messaging?

Note: It seems that future secrecy fails due to the ability to join a group just by knowing its GroupID.

Correct, this seems to be the issue. Since an attacker can join a group by learning some of the session states and thereafter compromise all messages due to being a part of the group, the group protocol lacks future secrecy.

From the paper (page 8 of the pdf): "After adding herself to the group, the confidentiality of future plaintext messages is compromised."

  Assuming that group update messages are properly authenticated, does future secrecy still fail for Signal's group messaging?

Due to the use of the double ratchet, it would retain that property if knowing the session state would not allow joining the group. But details matter in achieving that. It is not sufficient to just authenticate the group update since we are talking about a situation where the keys of one party are compromised.

However, you are right that it seems to be only the group administration that needs to be fixed.


Is it safe to hold key file's hash in application Title says all; Is it safe to hold key file's hash (MD5 or SHA1) in application (hard-coded)?

Thanks

The only danger is that the application now holds a fingerprint of your key. Thus enables the possibility to do some attacks, like bruteforce, and something to check against. And so it really comes down to the "same old question" as of how to keep your password-storage safe. If the key-file is a large one and somewhat random, then bruteforce is most certainly out of the feasible picture, however if it's not or the key-file is a common file or just a text-file containing a common word, the attack methods doesn't differ that much from what every webapp developer is trying to secure.


Why does TLS 1.3 use random-looking nonces for AEAD? In TLS 1.3, it seems that nonces for AEAD are constructed by XORing the recorded sequence number with the server/client_write_IV (which is generated during the handshake). Thus, nonces are random-looking and cannot be reused as the sequence number monotonically increases.

Why not just use the sequence number? Is there an advantage of having a random-looking nonce for AEAD? If not, how to explain this implementation choice?

As @CodesInChaos mentions in the comment, the purpose of the nonce randomization in TLS 1.3 is to combat multi-user attacks. That is, attacks where the adversary attacks multiple users simultaneously, and is happy as long as it breaks at least one user's connection without any regard to which user this is specifically. This motivation is explicitly called out in the RFC (Appendix E.2):

  In order to prevent mass cryptanalysis when the same plaintext is repeatedly encrypted by different users under the same key (as is commonly the case for HTTP), the nonce is formed by mixing the sequence number with a secret per-connection initialization vector derived along with the traffic keys. See [BT16] for analysis of this construction.

The idea of randomizing the nonce has received analysis in two academic papers:

Mihir Bellare and Björn Tackmann. The Multi-user Security of Authenticated Encryption: AES-GCM in TLS 1.3. CRYPTO'16. ePrint link
Viet Tung Hoang, Stefano Tessaro and Aishwarya Thiruvengadam. The Multi-user Security of GCM, Revisited: Tight Bounds for Nonce Randomization. CCS'18. ePrint link


Is there a security risk associated with using a PBKDF for an AES encryption key and Sha256 for a hash using the same password text? I am writing an encryption program using C#. My goal is to secure files even if the computer is stolen and somehow logged into.

Assumptions

The code used to write the program is visible to a malicious user
The password hash used in the program's login process is also visible

Concerns

I am using the same password to:

Derive an AES encryption key using Rfc2898DeriveBytes
Login to the software by comparing a stored SHA256 hash

I don't know if the stored hash can be used to figure out the encryption key

Notes

I use two different salts: one for the hash and the other for the key. I'm not sure if this really helps though because they are both stored in plain text along with the user's password hash.

Does using a PBKDF and a SHA256 hashing algorithm on the same password text present a security risk in a single computer application?

Yes, using a PBKDF and a SHA-256 hashing algorithm on the same password negates the usefulness of the PBKDF, by allowing to test a candidate password using a single hash; and (assuming unsalted password hash, which is not the case in the question) amortizing across multiple users/instances the computation of a rainbow table allowing to find the password quickly if its hash has been precomputed.

To make an analogy, imagine two safes, each with a 3-digit combination lock, and known to use the same 3-digit code. One safe contains valuables and uses a timed lock, preventing trying codes faster than one per hour; the other safe contains nothing and uses a non-timed lock. That second lock negates the benefit of the first one being timed, by allowing to quickly find the code for the first safe and extract the valuables.

With the unsalted SHA-256 of a mild password, a kid with a brain and web browser cracks it. Add some computing power, and the salted hash can be broken. Ask 10 random humans to pick a password they can remember a week later, and I bet at least one password succumbs to that attack.

While Rfc2898DeriveBytes is last century's password hashing / key stretching, it is still much less bad than plain hashing is. The order of magnitude of how less bad is the IterationCount parameter (and if there's no salt to the plain hash: times the number of users that an adversary is content cracking the password of).

For more efficient key stretching often available in practice, consider bcrypt or scrypt.


libsodium stream encryption I am new to cryptography, I have used OpenSSL and its aes-256-cfb cipher before to do stream encryption, which works great. Now I am going to try libsodium, since it's light and its APIs look concise, but I can't get it working.

I tried its XChaCha20 stream cipher, but it only has the crypto_stream_xchacha20_xor and crypto_stream_xchacha20_xor_ic functions, I can easily encrypt and decrypt messages when the message lengths appear in pairs, like encrypting 20 bytes, then decrypting 20 bytes, this works fine. but it will fail if encrypting 20 bytes, then decrypting 10 bytes and decrypting 10 more bytes. The latter case is what I want, I am implementing a proxy, I would like to read random length (i.e. not in blocks and no boundaries) of data from one TCP connection, encrypt and stream the data through another TCP connection, the other end of the connection reads random length of the encrypted data and decrypts it.

For what I want, xoring my data wouldn't work, since there's no context object like OpenSSL's EVP_CIPHER_CTX and no information like how many bytes have been encrypted/decrypted is kept, this looks weird to me, if it doesn't support this kind of stream mode, why is it called a stream cipher?

My question: Is it possible to do what I want using libsodium, if so, how?

libsodium has an API dedicated to stream encryption: crypto_secretstream, which is fully documented here: https://download.libsodium.org/doc/secret-key_cryptography/secretstream.html

Using simply crypto_stream_* or OpenSSL aes-256-cfb would be completely insecure. Without any authentication tags, the stream can be tampered with, without any ways to detect that it happened.

crypto_secretstream lets you encrypt and decrypt a sequence of variable-length messages, and prevents tampering, reordering and truncation.

However, if 50 bytes, then 20 bytes are encrypted, you must decrypt 50 bytes, then 20 bytes as well, in this order.

If you are reading data from a TCP connection, you can accumulate it into a fixed-size buffer, and once that buffer is full or you have reached the end of the stream, encrypt or decrypt its content. This will also improve performance and minimize the overhead of authentication tags over encrypting the outcome of ever single read() call.

If the session is interactive, your options are:

Pad messages to the chunk size (sodium_pad(), sodium_unpad()) before encrypting them. This uses more bandwidth, but improves security by revealing less information about the message sizes.
Prefix each ciphertext with its size, so you know how much data has to be read before being decrypted.


How to model a miniature elliptic curve? For educational purposes I would need to work on an elliptic curve that has a small field, but holds the safety futures of a real curve. Is that possible to have such a curve!?

For example for the curve of secp256k1, is that possible to find small $P$, $N$ and $G$ so that the mini curve does still have safety features of the real curve? By safety features I mean those features that come from the difficulty of solving the discrete logarithm problem. Of course I know that a curve with a small field is vulnerable through brute-force attacks.

To do so, first I read about properties of the prime $P$. It seems that it is a SAFE prime which is equal to $3 \bmod 4$. If I search for a small prime with the same two properties am I getting the correct mini curve?

How are $G$ and $N$ decided then?

I need a curve that lets me do point manipulations (adding, doubling, halving,...)  with plotable easy-to-work-with integers, not those 78-digits of secp256k1.

The curve parameters include:

$p$: The prime modulus of the underlying field

$a$ and $b$: These are used in the curve equation, $y^2 = x^3 + ax + b$

$G$: a point on the curve that generates a subgroup

$n$: the order (number of points) of that subgroup

Once you have decided on your $p$, the process is basically try different curve parameters and a point-counting algorithm to find a curve with a large, prime order subgroup.

You can do this all automatically using SageMath

Here is a script that will generate a curve for you with the given bit size: https://github.com/brichard19/ecdl/blob/master/scripts/gencurve.sage


How to check that an $km \times km$ block-binary matrix is an MDS matrix in $k$-bit words over $\operatorname{GF}(2)$ I have been reading about MDS matrices. It is defined as (paraphrased from Section 2.1)

An $n \times n$ matrix $M$ is MDS if and only if $bn(M) = n + 1$
where $bn$ (branch number) is defined as:
$bn(M) = \min_{u\neq0}({hw(u) + hw(Mu)})$ where $hw$ denotes Hamming weight.

It seems the MDS matrices like that of AES are defined over higher order fields like $\operatorname{GF}(2^8)$. It also seems the AES MDS matrix can be written as a matrix over $\operatorname{GF}(2)$. See this for example.
My question is, how does the MDS property translate to a binary matrix? Say, I am given an $n\times n$ binary invertible matrix, how can I understand whether this matrix is MDS or not?
I found some discussion in Section 2.1 about binary MDS matrices though, but could not get the idea.

Let $\bf A$ be an $n \times n$ binary matrix. Let we want to check that whether $\bf A$ is an MDS matrix over the finite field $\mathbb{F}_{2^k}$ for some $k$?
The necessary condition is that $k\mid n$ which means $n=km$ for some integer $m$.
Now Let $\bf A$ be $km \times km$ binary matrix. The first step is that to consider the matrix $\bf A$ as a block binary matrix as follows where ${\bf B}_{i,j}$, $1\leq i,j \leq m$ are $k \times k$ binary matrices.
$$
{\bf A}=
\left(
\begin{array}{c|c|c|c}
{\bf B}_{1,1} & {\bf B}_{1,2} & \cdots & {\bf B}_{1,m} \\ \hline
{\bf B}_{2,1} & {\bf B}_{2,2} & \cdots & {\bf B}_{2,m} \\\hline
\vdots & \vdots & \cdots & \vdots \\\hline
{\bf B}_{m,1} & {\bf B}_{m,2} & \cdots & {\bf B}_{m,m}
\end{array}
\right).
$$
Next, we should consider all square sub-matrices of the block matrix $\bf A$ and check that whether these sub-matrices are non-singular over $\mathbb{F}_2$? For example one of the square sub-matrices of $\bf A$ is as follows. The matrix $\bf C$ is an $2k \times 2k$ binary matrix and we should check its singularity over $\mathbb{F}_2$.
$$
{\bf C}=
\left(
\begin{array}{}
{\bf B}_{1,1} & {\bf B}_{1,2} \\
{\bf B}_{2,1} & {\bf B}_{2,2}.
\end{array}
\right).
$$
Note that if all square sub matrices of the block matrix $\bf A$ are non-singular over $\mathbb{F}_2$, then we say $\bf A$ is an MDS matrix over $k$-bit inputs or $k$-bit words.
Maybe you ask this question: Is $\bf A$ an MDS matrix over $\mathbb{F}_{2^k}$ for some irreducible polynomial of degree $k$ over $\mathbb{F}_2$? The answer is yes when $\bf A$ is obtained from an $m \times m$ matrix such as $\bf M$ provided that the entries of $\bf M$ belong to $\mathbb{F}_{2^k}$. Let me make an example to learn it more clearly.
Consider the following $4\times 4$ matrix where the entries of $\bf M$ belong $\mathbb{F}_{2^8}$ such that this finite field is constructed from the irreducible polynomial $f(x)={x}^{8}+{x}^{4}+{x}^{3}+x+1$  over $\mathbb{F}_2$ (some users of this forum maybe say it is the MDS matrix of AES, but imagine we do not know this fact and we want to check it!).
$$
\scriptsize{
 {\bf M}=
 \left(
 \begin {array}{cccc}
 \alpha&\alpha+1&1&1\\
 1&\alpha&\alpha+1&1\\
 1&1&\alpha&\alpha+1\\
 \alpha+1&1&1&\alpha
 \end {array}
 \right).}
$$
Now we obtain a $8 \times 8$ binary matrix such that its characteristic polynomial over $\mathbb{F}_2$ is equal to $f(x)$ such as the following one
$$
\scriptsize{
{\bf N}=
 \left(
 \begin {array}{cccccccc}
 0&0&0&0&0&1&0&0\\
 0&0&0&0&1&0&0&0\\
 0&0&0&0&0&0&1&0\\
 1&0&0&0&0&0&1&0\\
 0&1&0&0&0&0&0&1\\
 0&1&0&0&0&0&0&0\\
 0&0&0&1&0&0&0&0\\
 1&0&1&0&0&0&0&0
 \end {array}
 \right).}
$$
Next, by applying $\bf N$ we transform $\bf M$ to a $32 \times 32$ binary matrix, denoted $\bf A$, as follows. Let the $(i,j)$ entry of $\bf M$ be $\sum_{i=0}^{7}b_i\alpha^i$ where $b_i$'s are binary numbers. Now the $(i,j)$ entry of the block matrix $\bf A$ is equal to $\sum_{i=0}^{7}b_i{\bf N}^i$ in modulo 2. Therefore, the block matrix $\bf A$ is given by
$$
\scriptsize{
\left(
 \begin {array}{cccccccc|cccccccc|cccccccc|cccccccc}
 0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\
 0&0&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0\\
 0&0&0&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0\\
 1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0\\
 0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0\\
 0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0\\
 0&0&0&1&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0\\
 1&0&1&0&0&0&0&0&1&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1\\ \hline
 1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0\\
 0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0\\
 0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0\\
 0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0\\
 0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0\\
 0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0\\
 0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0\\
 0&0&0&0&0&0&0&1&1&0&1&0&0&0&0&0&1&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1\\ \hline
 1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0\\
 0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&1&0&0&0\\
 0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&1&0\\
 0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0\\
 0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1\\
 0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0\\
 0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&1&0\\
 0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&1&0&1&0&0&0&0&0&1&0&1&0&0&0&0&1\\ \hline
 1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\\
 0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\
 0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0\\
 1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0\\
 0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1\\
 0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0\\
 0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0\\
 1&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&1&0&1&0&0&0&0&0
\end {array}
\right).}
$$
The final step is that we check the singularity of all square sub-matrices of the block matrix $\bf A$ over $\mathbb{F}_2$ (the number of these sub-matrices are ${2n\choose n}-1$, for example for AES is 69).
Maybe you ask this question what is the advantages of this scenario. One answer is that the computation over $\mathbb{F}_2$ is more faster than the finite fields.
I hope you find this answer helpful.


Low Encrypted Entropy on PDF File Thank you for the answers, I have edited my questions.
It is a known fact that encrypting the files increases the file entropy. You can see the average entropy values of encrypted and non-encrypted versions of the different files in this
paper (see figure 2). After I read this paper I check out my encryption algorithm and I notice that I was using base64 encoding while overwriting the file and that was decreasing the file entropy. So my problem is solved.

As bmm60 comments, its not clear that the entropy has gone down. There are many forms of encryption that still preserve some level of information about the input (the encrypted version of a bitmap under a block cipher using ECB is a good example). It's also possible that your encryption product adds unencrypted metadata to a file and if there's a large amount of metadata relative to the file size and the metadata is of a very stereotyped form (such as English readable ASCII) then this will have less entropy than the pdf format.
Without more detail on the input and encryption method, there is a limit to what can be said.
UPDATE: According to the description of PDF encryption in this Black Hat talk 256-bit AES-CBC is used. For lengthy plaintexts this should remove bytewise structure and the bytewise entropy should tend towards 8-bits for larger texts. However, the talk also says that PDF encryption only encrypts some of the objects in PDF's Carousel Object Structure and the other objects are unencrypted, largely human readable, markup language which might have a bytewise entropy of only 4-5 bits (English language words have a bytewise entropy in this range). Therefore if the input file is quite short or has a lot of object structures that are neither stream nor strings, the entropy will be closer to this figure. For pdfs with more pages (and hence larger string and streams sections) the entropy should be closer to 8-bits.
Thanks to kelalaka for pointing out the Black Hat talk.


Why does Apple create a certificate for my push notification key Brief rundown of how Apple Push Notifications (APN) work:

Generate a keypair, generate a CSR for it
Upload the latter to your Apple Developer account and associate it with your mobile app
In the process, your CSR is signed and you get to download the certificate
Connect to the APN server using the key + certificate, send your notifications

Note that this is a separate key/certificate just for push notifications. It is distinct from the code signing key, and not used anywhere else. And, TTBOMK, the mobile phones never see that key, they verify that push notifications are genuine based on the fact that they receive them via a secure channel from the Apple HQ.

Here is my alternative, simpler idea: create a keypair and upload the public half to Apple. You can then send messages by authenticating with the private key.

So, why does Apple sign my key? What do I actually use the certificate for, while connecting? Is that signing dance done because SSL supports client certs but does not support bare private keys?

I'm not a cryptography expert, so please correct any wrong assumptions I've made!

I'm guessing that the need for a certificate has nothing to do with authenticating the upload, but so that people's iPhones can authenticate the app at install time / runtime.

[Ah, I see your edit that this is not right. I'll leave it here for posterity anyway. Are you sure you can't find documentation for this somewhere?]

As a developer, you create code-signing keys for yourself.
You announce to Apple "Yo Apple, I'm the developer of this app, and here's my code-signing key".
Apple makes a certificate out of your public key, telling the world that Apple agrees that you are the rightful developer of this app.
Apple distributes this certificate along with your app to millions (we hope!) of end-users who download your app.
Any update you push must be signed by the same code-signing key as the original, otherwise the end-user iPhones will reject it. (How to you prevent malicious updates and NSA-style sideloading?)

I'll also address this part of your question:

  Is that signing dance done because SSL supports client certs but does not support bare private keys?

No, SSL does not support "bare private keys" and here's why: how do I know who the private key belongs to? Any bloke can walk up and say "Hi, I'm Christian Aichinger, here's my public key, and I'm going to use the corresponding private key to sign some data". Ok, fine, but how do I know that I'm talking to the real Christian Aichinger, and not somebody pretending to be them.

The commonly accepted way to solve this is to have some third party that we both trust verify that you are who you say you are, and that this public key does in fact belong to you. That trusted third-party is called a Certificate Authority, and that statement that this public key belongs to you is called a Certificate.


Is it possible for a simulator to always abort? In this paper of J. Baron, et al. (PDF), simulator always aborts the ideal functionality before client outputs its pattern-matching result obtained from the ideal functionality. (See bottom of page 30, and top of page 33)

My questions are:

Why should simulator always abort?
While simulator always abort, is it possible for adversary to distinguish between ideal and real worlds? Since, in ideal world simulator always abort and client will never output anything.

This is very strange, and somewhat suspect. The abort here is one that prevents the client from getting output. However, the real-world adversary may behave in a way that the client does get output. I suggest writing to the authors to ask and/or going through this very carefully. Without having gone through the details at all, my initial guess is that this doesn't seem right. Having said that, I didn't check it at all (and this section does say "Initial...", so maybe this is just part of the simulation).


What's the perfect chain length : number of chains ratio for rainbow tables? I'm building a SHA-1 rainbow table to crack basic passwords (i.e. up to 10 character, 0-9,a-z), but I can't seem to calculate that golden ratio that would give me the most coverage. What ration of chain length to number of chains should be chosen?

Also is there anyway to estimate the coverage of the table? As at now, after building the table I'm using a brute-force attack to check it's coverage. It's a very inefficient way.

I'm building a SHA-1 rainbow table to crack basic passwords (i.e. up to 10 character, 0-9,a-z), but I can't seem to calculate that golden ratio that would give me the most coverage. What ration of chain length to number of chains should be chosen?

That choice is not really about coverage, but (mainly) about how much space you are willing to use. You should choose the number of chains based on how much space you can use, since each chain uses a constant amount independent of its length. Then you can choose the chain length to get the coverage you need or based on the amount of computational effort you can spend on creating the table.

  Also is there anyway to estimate the coverage of the table?

Yes. You will find a formula for the probability of success in the seminal paper by Philippe Oechslin (pdf):

  The probability of success within a single table of size $m × t$ is given by:

  $$P_{table} = \Pi_{i=1}^{t} (1 - \frac{m_i}{N})$$
  where $m_1 = m$ and $m_{n+1} = N (1 - e^{-\frac{m_n}{N}})$

Note that in your case you will likely not be able to generate a rainbow table with good coverage unless you invest quite a bit of effort. Your search space is larger than $35^{10} \approx 2^{51.3}$, so to get even 50% coverage you would need to compute more than $2^{50}$ hashes, taking several years of CPU time with a typical desktop CPU.

As long as your coverage is low you can get a decent approximation by assuming you have no collisions, i.e. just divide the product of chain count and chain length by the size of the search space.


What is the impact of a server not fully verifying the data in the Client Finished packet of a TLS connection? F5 BIG-IP devices suffer from a vulnerability in which not all bytes of the Finished packet in a TLS connection are validated. The sort-of technical description can be found here. F5 don't consider it a vulnerability, so they won't patch it, and it is currently causing me a headache right now for PCI compliance reasons. At the moment nobody seems to agree on whether there's a bug or not, and there's not really a clear explanation of the actual impact and attack requirements.

My understanding is that the Client and Server Finished packets in TLS are designed to post facto mutually authenticate the handshake messages, including the master secret key exchange. My thought process is that, if an attacker were to man-in-the-middle the TLS connection, they could leverage this vulnerability to downgrade the connection by spoofing the Client Finished packet, or possibly even compromise the master secret. I'm unsure as to how the process would go from there, with the validation of the Server Finished packet on the cient.

Assuming that some arbitrary number of bytes in the Finished packet are not properly validated, what's the real impact of this vulnerability? With this bug in play, does the security of the connection mostly rely on the client's validation of the Server Finished packet?

Suppose the server does not check the Client Finished value.  This means that the MITM could change some handshake messages and the server would not know this (e.g., downgrade, as you mentioned).  So, you could use this to fool a server that doesn't check the Client Finished value.

If n bits are checked by the server, you have a 1/2^n chance of getting the Client Finished value right by random chance.  You might be able to predict the remaining client messages and then use brute force to try different random handshake modifications offline until one generates the correct finished bits in the n locations that the server will validate.  This will take about 2^n tries, which for small n is feasible.  By sending this handshake sequence you can fool the server into thinking the client sent the modified handshakes.

Now, the server sends back a Server Finished message, which includes a hash of all the messages the server has seen, including the Client Finished value.  Your modified handshakes will completely change the hash value for the Server Finished.  As a result, you're stuck having to brute-force all the bits that the client checks in addition to those the server checks.  If the client is lazy and only checks m bits, then overall you're looking at 2^(n+m) tries, which might be feasible.  However, if the client validates the full server finished, you'll have to break all 12 bytes, or 96 bits, which won't be easy to brute force before the connection times out.

Security (defined here as the number of brute force attempts to get the two Finished messages to validate) depends roughly on the total number of bits the client and server check, so if the server does not check any bits then the security relies, as you said, on the client's validation of the Server Finished message.

You mentioned changing the master secret.  This could allow the MITM to create a valid connection to the server (e.g., if RSA key exchange is used).  However, the MITM does not know the master secret the client is using, since the server private key is required, so for the Server Finished message you have the problem of determining the encryption and MAC keys.  If you negotiate a weak cipher suite with the client, this might be easier than brute forcing the Server Finished message.

Other attacks may be possible based on the configuration of the client and server, so it's best if the server fully validates the Client Hello to mitigate them.


What's the difference between single key-pair public key encryption and proxy re-encryption? Proxy Re-Encryption provides the ability to transform a ciphertext encrypted under some key to the one under another key.
This seems interesting. But, something seems strange.

Suppose Alice has a key pair (sk_a, pk_a) and Bob also has a key pair (sk_b, pk_b). If Alice and Bob generates a proxy re-encryption key to transform a ciphertext under pk_a to the one under pk_b and vice versa, they can send message without revealing their secret keys.

At this point, what about the following scenario?
Bob securely transmits his public key pk_b to Alice. Then, Alice encrypts her message vy using pk_b. There is no need to transform the ciphertext.
Also, Alice can send Bob her public key pk_a when she wants to receive the message from Bob.

What is the advantage of proxy re-encryption?
I think there is no potential difference between standard public key encryption scheme and proxy re-encryption.

With two parties, using proxy re-encryption does indeed not make much sense. It becomes interesting when there are more parties. For example, suppose you receive encrypted mails, that transit through a server. Then you could want to forward one of your encrypted mails, stored on the server, to someone else (say, Bob). With a proxy scheme, you can just ask the server to convert this encrypted mail into a mail encrypted with the key of Bob, and to send it to Bob. In general, it provides a convenient way of managing databases of encrypted files in a multi-user scenario.

You can find more applications in the introduction of any paper on proxy re-encryption. For example, page 3 of this paper discusses examples in more details. This paper also mentions other applications (with references) in the third paragraph of its introduction.


Best practice to create certificate by CA I suppose that I have this scenario:

Root CA
Intermediate CA

Practice 1:

The Root CA generates her own $PK_r$ and $PB_r$ key, and after it makes her certificate $Cert_r$.
The Intermediate CA generates her own $PK_i$ and $PB_i$ key, and after it generates a Certificate Signed Request (CSR), and send it to the Root CA to obtain a Certificate $Cert_i$.

Practice 2:

The Root CA generates her own $PK_r$ and $PB_r$ key, and after it makes her certificate $Cert_r$.
The Intermediate CA makes a request of a certificate $Cert_i$ to the Root CA, and this last creates a key pair ($PK_r$ and $PB_r$ key) and send to Intermediate CA the certificate requested. In a second moment, the Root CA send (i.e. with an email) the key pair to Intermediate CA.

I'm using xca to test and understand what is the best practice.

Practice 1 is superior without a doubt.

First and foremost the obvious problem:
With practice 2 you need a channel to transport a piece of data confidential and authenticated which is strictly harder than just transport information (the CSR) authenticated for practice 1.

Now there are a couple of other reasons why in practice the first practice is used:

In actual CAs, the private keys are stored inside of HSMs. If you were to transport a key from the root CA HSM to the Intermediate CA HSM these two would have to be linked in some form / initialized the same way which is unneccessary procedure and unneccessary risk, after all if someone manages to convince the root-HSM to give you a wrapped key of the root key, now the attacker can use this key on the fortified root-HSM or he could use it on the less-fortified intermediate-HSM. Note though that actual CAs most likely do operate multiple HSMs that can unwrap the root keys, but they are all off-line, in-vaults and highly fortified as opposed to the intermediate HSMs which sometimes even operate fully automatically with an internet-facing API / service.
At other times the intermediate CA may not be operated by the same company as the root CA. In these situations I highly doubt that the client (the intermediate CA) would want to trust the root CA's security measures on key generation and wrapping and secure transport methods given that they might as well just generate a key on their own and use a CSR.
It introduces unneccesary protocols. Consider how end-users get their certificates: They generate a key themselves, send a CSR and get a certificate. No sane CA would ever propose to generate the keypair for the client and have them download it. The same applies to this CA-CA communication: The protocol to issue certificates works just fine, so why make it harder?


Three different numbers with x³=x mod p p is a prime greater than 2 and $a \in \mathbb{Z}_p$. Why are there exactly three solutions for a³ = a mod p?
Obviously 0 and 1 are both in $\mathbb{Z}$ and valid solutions, but that still means, there is one element (and only one) missing. I can't figure out which one and neither do I understand why there could not be more valid solutions. Any tips?

Unless otherwise stated, $a$ is any integer representative of an eponymous element of $\mathbb{Z}_p$.
$$\begin{align}
a^3\equiv a\pmod p
&\Longleftrightarrow a^3-a\equiv0\pmod p\\
&\Longleftrightarrow a\cdot(a^2-1)\equiv0\pmod p\\
&\Longleftrightarrow a\cdot(a-1)\cdot(a+1)\equiv0\pmod p\\
&\Longleftrightarrow\begin{cases}
a\equiv0\pmod p&\text{ or}\\
a-1\equiv0\pmod p&\text{ or}\\
a+1\equiv0\pmod p
\end{cases}\end{align}$$
The last step uses that since $p$ is prime, if it divides the product of some integers [here: $a$, $a-1$, and $a+1$ ], then it must divide at least one of these integers. The reverse trivially holds without the hypothesis that $p$ is prime.

Since $p$ is greater than $2$, the three solutions $a\equiv0\pmod p$, $a\equiv1\pmod p$, $a\equiv p-1\pmod p$ are distinct elements of $\mathbb{Z}_p$.

Without the hypothesis that $p$ is prime, there can be additional solutions to $a^3\equiv a\pmod p$; for example, $a^3\equiv a\pmod{15}$ holds for nine out of fiteen elements $a$ of $\mathbb{Z}_{15}$.

Keep in mind that $x\equiv0\pmod p$ means exactly the same as: $p$ divides $x$.

Thanks to CGFoX for having corrected the $a\cdot(a^2-1)$ expression.


How to efficiently generate a random safe prime of given length? A prime $p$ is said to be safe prime if $(p-1)/2$ is also a prime. How to efficiently generate a safe prime? I have written the following code in sagemath which generates a random safe prime of 1536 bits. This code took 426 seconds to generate a safe prime. That's very inefficient. Is there a faster way to efficiently generate a safe prime?

while True:
    p = random_prime(2^1536-1, false, 2^(1535))
    if ZZ((p-1)/2).is_prime():
        return p

There is no more efficient way of generating a safe prime. Even in OpenSSL's optimized code, it can take a long time to generate a safe prime (30 seconds, a minute, 2 minutes). Run "openssl gendh 1024" on your computer to see (on my 2015 MacBook pro it can take a long time, but the variance is really high so try a few times).

The comments talk about safe primes for RSA. Indeed, safe primes are not needed for RSA. However, they are needed for generating parameters for finite-field cryptography (Diffie-Hellman over a finite field), and for other applications in cryptography. For example, zero-knowledge range proofs use a group with an unknown order, and this is defined by an RSA modulus and Pedersen commitments over that modulus. When using safe primes, this ensures that the group is large and furthermore that a random group element is a generator with overwhelming probability. See Section 1.2 of Efficient Protocols for Set Membership and Range Proofs for more about this particular application.

So, in more advanced cryptography, there are plenty of applications for safe primes (indeed, RSA encryption is not one of them).


Which is the most secure steganography technique? Just like we have AES in crypotography, which is the most secure technique in Steganography?
I am looking for a technique in which the standard image characteristic modifications it does go undetected(as yet).
This question is regarding image steganography and I want to store few bytes of information.

Steganography is in general impossible, and most "practical" schemes do not work. If you are really interested in the area, however, there was some work done about a decade ago on provably secure steganography. It relies on an understanding of the distribution of the messages, which is what makes it very problematic in practice.

Here are a couple of works to get you started:
https://www.cs.cmu.edu/~biglou/PSS.pdf and
http://cs.brown.edu/~anna/papers/lysmey06.pdf.

I stress, however, once again: practical steganography schemes are broken. They can typically be easily distinguished using basic machine learning tools.


What is customizable in ECDSA signature and verification? Let's say I make a signing and verification ECDSA modules. Signing module receives plain message and outputs signed message. Verification module takes signed message and checks consistency.

Theoretically which things should be known to both modules:

Padding scheme for message
Hashing function
Scheme for combining message and signature

Something else?

Additionally signing module should know the private key, and verification module the public key. How these keys were generated (parameters used, such as curve used) is irrelevant to signing and verification modules?

Theoretically which things should be known to both modules:

Padding scheme for message

As mentioned in the comments, the 'padding scheme' for ECDSA is either fixed or arguably nonexistent.  You take the hash value, zero extend it if it's smaller than the group size, you take it modulo $q$ if it's bigger than the group size, and then fit that integer into the ECDSA equations.

Hashing function

Yes, bare ECDSA signatures and public keys have no way of indicating what hash function is used.  IMHO, it should be listed in the public key; it isn't (at least in my experience)

Scheme for combining message and signature

Well, you appear to be under the impression that we always attach the signature to the message.  Sometimes this is true, as in PGP. However sometimes this isn't true at all, for example, if we are using signatures to authenticate IKE; there, the value we sign is actually derived from the contents of a previous packet, hence we can't say that the message and the signature are combined at all.
What I've seen in practice is that we separate out the protocol level stuff (how are messages and signatures transported; there are a lot of varients used in practice) and the crypto stuff (how to do ECDSA); for example, on the verification side, there is some upper layer that somehow obtains the message and the signature, and then presents them both to the verifier.

Something else?

Apart from the public and private keys that you mentioned:

The actual curve being used; that is far from irrelevant to the crypto module.

The format of the signature; I've seen two variants; one is to just paste the $r$ and $s$ integers together (using a fixed length for both); the other is to ASN.1 encode it as a sequence of the two integers.  Now, it's possible that the protocol-level logic that I mentioned before would standardize that...


EC ElGamal versus static+ephemeral ECDH A client application needs to encrypt a UDP datagram for a server with known EC public key $P$. Performing a full ECDH key exchange would defeat the benefit of using UDP as a connectionless protocol. I am therefore looking at ways to share a temporary symmetrical key decided by the client only.

Two solutions to that constraint seem to be :

Generating an ephemeral key pair $(k,K)$, and encrypt the payload with $kP$ − ECDH.
Generating a random key $r$ and encrypt it with EC ElGamal.

The ECDH approach requires 1 EC multiplication from the client ($kP$), 1 EC point to include in the datagram ($K$), and 1 EC multiplication from the server ($pK$).

According to the link above, the EC ElGamal approach seems to require 2 EC multiplications from the client, 2 EC points to include in the datagram, and 1 EC multiplication from the server.

Diffie-Hellman is apparently lighter in computation and header data. What is the advantage of using ElGamal ?

ElGamal appears to be used instead of Diffie-Hellman (or IES) in OpenPGP mostly because when that format was put together, there were some unresolved intellectual property issues surrounding both RSA and Diffie-Hellman, while ElGamal was unproblematic. This trend for ElGamal seems to stick around, mostly by force of habit, e.g. when switching to elliptic-curve variants.

If you look at ElGamal closely, you will see that it is, in fact, a Diffie-Hellman key exchange, where the resulting key is used to encrypt a message in a kind of one-time-pad system (the $y^r$ value is the DH output, and is combined, using the group operation, with the message to encrypt). Using the group operation allows for homomorphism, but when that property is not needed, it is a useless complication and overhead.


Time gap between Diffie-Hellman Key Exchange and ElGamal encryption? I'm looking into the Diffie-Hellman key exchange paper (New Directions in Cryptography, 1976) as part of a series of classic papers in Cryptography for my Ph.D and I was wondering if someone could give a reason for something that has always seemed very strange to me.

ElGamal seems like a natural thing to immediately try, so it seems odd that there was a nine year gap between this paper and the introduction of ElGamal (to the best of my knowledge, 1985). Was there a theoretical reason for this? Or was it simply "not spotted".

Actually, if you read Diffie and Hellman's paper closely, you'll see that they explicitly talk about taking another's party value from a public file. Thus, it really already does public-key encryption. However, they didn't call it that, and people didn't view it as public-key encryption, but rather as key distribution.

The reason for this is that at the time, the understanding was that public-key encryption required a "trapdoor function" that can be inverted using the secret key. In fact, this is how Diffie and Hellman defined it, and thus they couldn't achieve it.

Now, El Gamal explicitly stated that the technical construction is just Diffie-Hellman. However, his conceptual contribution is enormous; he recognized that public-key encryption does not need to be an invertible function. By the way, the majority of his paper is about the digital signatures and this is novel.

This discussion raises an interesting point which is that some important results are completely non-technical and are important because they make us look at things differently. This is exactly what the El Gamal paper did.


CSIDH Squaring Fixing the Base Curve Consider the following variants of the CSIDH squaring problem.
P1. Given $sE, E$ where $s$ is a random ideal class and $E$ is a random curve (reachable from initial $E_0$), find $s^2E$
P2. Given $sE_0$ where $s$ is a random ideal class and $E_0:y^2=x^3+x$ is a fixed initial curve, find $s^2E_0$.
Of course, there's also the decisional variant:
DP1. Given $sE,tE,E$ where $E$ is a random curve as above and $s,t$ are either i.i.d. sample of ideal class or $s^2=t$, decide which.
DP2. Given $sE_0,tE_0$ where $E_0:y^2=x^3+x$ and $s,t$ are either i.i.d. sample of ideal class or $s^2=t$, decide which.
What do we know about the hardness of (D)P1 compared to (D)P2? Are they even comparable?
I would also like to stress that, for another equivalent problem called the inverse problem stated in P3, fixing the base curve to $E_0$ would weakens P3 to P4 as easy as finding a quadratic twist. However, computing quadratic twists would only reduce (D)P2 to itself. So it is not so obvious whether the hardness of (D)P2 is weaken.
P3. Given $sE,E$ find $s^{-1}E$.
P4. Given $sE_0$ find $s^{-1}E_0$.

If you have a solver for P1, then it can also solve P2, so the problems are comparable: P2 is easier.
P1 is assumed hard, and is used as the basis of, e.g. https://eprint.iacr.org/2020/1012.
P1 is known to be generically equivalent to P3 (see https://hal.archives-ouvertes.fr/hal-02373179 and https://eprint.iacr.org/2020/1012), however P2 is probably not equivalent to P4: the reduction does not work for these more constrained problems, and P4 is known to be easy, whereas P2 is likely not.


Convert old and busted password encryption to something sensible Given a TOTALLY HYPOTHETICAL scenario in which passwords for over a million accounts in over 200 databases have been stored using 3DES, a key derived from a (single) MD5 hash of a customer-controlled (rarely changed from the default) pass-phrase, a hard-coded IV (same for every account in every database), and a ciphermode of CFB...

Would it be safe enough (and not totally asinine) to wrap a separate hash mechanism (and salt) around the old encrypted value to introduce some concept of security? If so, would it then be possible to determine if the resulting stored-password is the new type or the old type?

My end goal is better password security and the ability to, on a per-user basis, update their password to the new model immediately after they authenticate.

Sysadmins have switched from one password hash algorithm to another many times.
There is a standard process for this switch.

The Modular Crypt Format (MCF) is the standard scheme for formatting encrypted passwords, as used by passwd, crypt, etc.
(see Why are there $ signs in my passwd file? ).
MCF uses a single column to store the password hash algorithm and the hash of the password (etc.).
I don't understand why other answers seem to think you need to add a new column -- that seems non-standard and I don't see any benefit over doing it the standard way.

  would it then be possible to determine if the resulting
  stored-password is the new type or the old type?

Yes. If you use MCF for storing the password hash (and why wouldn't you?), it's pretty obvious whether a stored password hash is the new type or the old type.

As explained in Wikipedia: crypt (c) and Wikipedia: passwd, the printable form of new password hashes begins with dollar-digit.
Currently the most widely used password hash algorithms produce a printable form that begins with "\$2y\$", "\$5\$", or "\$6\$".

It is likely that you are storing password hashes in a form that never begins with a dollarsign, and so it will be pretty trivial to determine whether it is the old type or the new type.

If someone, in a TOTALLY HYPOTHETICAL scenario, currently stores password hashes in a format incompatible with MCF, perhaps that person could assign "\$0\$" to represent his old hash algorithm, and convert to a MCF by pre-pending that "\$0\$" to the beginning of all his old-style passwords (and tweaking his login-system so that it recognizes that "\$0\$" as indicating the old password hash algorithm).
There's a way to gradually make this change a little at a time, in a way that each step leaves the system in a "working" configuration where people can still log in.

As I may have said before at " Do I have to recompute all hashes if I change the work factor in bcrypt? ",

Rehash passwords one at a time, as people log in

Many UNIX-like systems are already set up so the sysadmin can change the "preferred" password algorithm, work factor, and salt length at any time.
Later, whenever a user logs in by typing their password, the system updates that user's row in the passwd file to use the system's current "preferred" work factor etc.
See a, b, c, d, e, f, g, h, i, j, k, L, m, n, o for how to tweaking the appropriate configuration file in order to set the "preferred" algorithm etc.
Typically this involves pluggable authentication modules (PAM).

Many passwd files (or thier equivalent) store, for each user,
not only the the salted hash,
but also the user-unique salt, the ID of the hashing algorithm used, and the work factor
(often dollar-sign delimited).
That allows us to gradually switch to a completely different password hash algorithm and salt width.

details:

For example, let's say we want to switch from inadequate amounts of salt and some obsolete hash to bcrypt with a work factor of 11.
The sysadmin sets the "preferred" algorithm, salt, etc. to "bcrypt with a work factor of 11", etc.

The next time a user logs in, resets their password, or changes to a new password -- i.e., uses the login or passwd programs -- those programs:

1) Hold on to the plaintext password the user typed in for a few moments.

2) Check the passwd file to see if that user's hash already uses the latest algorithm, work factor, and salt width. If so, continue with 4.

3) Authenticate the user with whatever old, obsolete algorithm the passwd file indicates for that user. If successful, additionally create a unique new salt with the latest salt width.
Run that salt, and the plaintext password that we're still holding on to, through "bcrypt with a work factor of 11" (or whatever today's preferred algorithm is) to get the new hash.
Update the passwd file for that user with the new hashing algorithm ID, the new work factor, the new salt, and the new hash.

4) Authenticate the user with the shiny new algorithm the passwd file indicates -- the latest algorithm, work factor, and salt width.

5) Then the server must forget the plaintext password.

After a month or two, if some rows of the passwd file still indicate some old, obsolete hashing algorithm and work factor -- i.e., those users haven't logged in for a month or two since you made the change -- you might send them a mail or call them on the phone and ask them nicely to log in soon.

After a few months, if there's still some user whose row of the passwd file still indicate some obsolete algorithm -- i.e., that user hasn't logged in for months -- perhaps you could reset that password and generate a new random unguessable password, more-or-less the same as if that user had forgotten the password and gone through the normal "I forgot my password" process.
If the user ever comes back, go through the normal "I forgot my password" process again to reset the password back to whatever the user wants to use.

See "Migrate old md5 passwords to bcrypt passwords"
for more discussion of this approach.

EDIT:

Modular Crypt Format is now common enough to be a de facto standard.

However, because it doesn't have an "official" standardization document, some argue that it isn't a "real" standard:
"Modular Crypt Format: or, a side note about a standard that isn't".

I recently learned that the LDAP / RFC2307 Hash format does have an official standardization document (RFC2307).
According to
passlib.hash - Password Hashing Schemes,
The LDAP / RFC2307 Hash format "the basic format {SCHEME}HASH has seen widespread adoption in a number of programs."


Secure double encryption using CPA and CCA Do you mind if you give me any hints, links or ideas about how to improve the security of double regular encryption and decryption, by using CPA game and CCA game, it sounds interesting question, and I'm still discussing it with my classmate. Given the following info,

The key generation algorithm $(PK, SK) \leftarrow Gen(1^λ)$:

Compute $(pk, sk) \leftarrow gen(1^λ)$
Compute $(pk', sk') \leftarrow gen'(1^λ)$
Set $PK := (pk, pk')$ and $SK := (sk, sk')$

The encryption algorithm $C \leftarrow Enc(m)$:

Compute $c \leftarrow enc(m)$
Compute $C \leftarrow enc'(c)$

The decryption algorithm $\tilde{m} \leftarrow Dec(C)$:

Compute $\tilde{c} \leftarrow dec'(C)$
Compute $\tilde{m} \leftarrow dec(\tilde{c})$

If both $\pi$ is CPA-secure, then will the new scheme $\Pi$ be CPA-secure? If so, please
prove it. If not, please disprove it. Same as for CCA.
Kind Regards

For CPA security it is actually enough that the first scheme, i.e., $\pi = (gen, enc, dec)$ is CPA secure.

Lets define the CPA game of a general scheme $\pi = (Gen, Enc, Dec)$ against an adversary $A$ as follows:

We sample $(pk, sk) \leftarrow Gen(1^\lambda)$, and send $pk$ to $A$.
$A$ outputs messages $m_0$ and $m_1$.
We sample $b \leftarrow \{0,1\}$ (a random bit), and $c \leftarrow Enc(pk,m_b)$ (here I add the public key as a parameter to $Enc$, to make the key explicit)
$A$ outputs a bit $b'$.

We say $A$ wins if $b = b'$, and the scheme is IND-CPA secure if $A$ has at most negligible advantage.

Now, let $\Pi = (Gen, Enc, Dec)$, $\pi = (gen, enc, dec)$ and $\pi' = (gen', enc', dec')$ be the schemes you suggest in your question. Assume there exists an adversary $A$ with non-negligible advantage against $\Pi$ (i.e., proving $\Pi$ is not IND-CPA secure). Then we can construct an adversary $B$ against $\pi$ as follows:

On input $pk$ from the CPA game $B$ samples $(pk', sk') \leftarrow gen'(1^\lambda)$, and sends $PK = (pk, pk')$ to $A$.
When $A$ outputs $m_0$, $m_1$ $B$ forwards these messages to the CPA game.
On input $c$ from the CPA game $B$ samples $C \leftarrow Enc'(pk', c)$ and sends $C$ to $A$.
When $A$ outputs $b'$ $B$ outputs the same bit.

Now you see that $B$ wins the CPA game against $\pi$ if and only if $A$ would have won the corresponding game against $\Pi$. This means that since $A$ has non-negligible advantage against $\Pi$ and $B$ has provided $A$ with messages exactly as in the CPA game against $\Pi$, it follows that $B$ must also have non-negligible advantage against $\pi$. This, however, contradicts $\pi$ being IND-CPA secure, so no such $A$ can exist. I.e., $\Pi$ is also CPA secure.

Note the security of $\pi'$ really does not matter here.

A similar proof might be possible for CCA security, but I have not attempted one.


Do we always use Sophie-Germain primes $1\bmod 4$? A prime $p$ is Sophie Germain if $2p+1$ is also prime. Wiki says if $p\equiv3\bmod4$ then $2p+1|2^p-1$. This seems to put a huge restriction on density of Sophie-Germain prime if they are $3\bmod4$. For this reason do all systems use Sophie-Germain primes with $1\bmod 4$ for discrete logarithm?

This seems to put a huge restriction on density of Sophie-Germain prime if they are $3 \bmod 4$.

I'm not sure how you come to that conclusion; whether $2p+1$ is a factor of $2^p-1$ would not have any immediately obvious consequence to $2p+1$ being prime.

  For this reason do all systems use Sophie-Germain primes with $1 \bmod 4$ for discrete logarithm?

Actually, Sophie-Germain primes of the form $3 \bmod 4$ would appear to be more prevalent; for example, the primes listed here are all of the form $3 \bmod 4$.  One reason is that it makes the value $g=2$ be a quadratic residue, that is, its use during the DH operation doesn't leak the lsbit of the private exponent, and that's appreciated by some people.


What does the term "asymptotic security" mean? The Stellar cryptocurrency whitepaper lists "asymptotic security" as a key advantage over other consensus protocols (for example, proof-of-work in Bitcoin). What do they mean by this? As I understood it, it refers to guaranteed safety, as in: results valid and identical at all nodes. However, this can't be guaranteed for a decentralized system, as any node can join the system and refuse to accept the state presented by other nodes. So they must mean something else…

What does the term "asymptotic security" mean?

Here is an excerpt from the whitepaper where they vaguely characterize asymptotic security:

  Safety rests on digital signatures and hash families whose parameters can realistically be tuned to protect against adversaries with unimaginably vast computing power.

One of the key ideas of cryptography is to provide security by means of operations that are (relatively) affordable to honest parties but prohibitively costly to adversaries.  So one thing you see over and over in cryptographic literature is efforts to quantify the cost to adversaries to break some proposed cryptographic scheme.

Asymptotic security is one paradigm for so doing.  In such an analysis, one states the adversary's cost as a function of a designated security parameter (e.g., key length).  The scheme is then said to be secure if an only if the adversary's advantage is a negligible function of the security parameter.  Very informally, an asymptotically secure scheme is one that's been conditionally proven to be harder than any polynomial for the attacker to break.

What the author seems to be highlighting is that alternatives to their proposal don't enjoy this "harder than polynomial" property (pp. 2-3):

  Finally, in contrast to traditional cryptographic protocols, proof of work offers no asymptotic security. Given non-rational attackers—or ones with extrinsic incentives to sabotage consensus—small computational advantages can invalidate the security assumption, allowing history to be re-written in so-called “51% attacks.”

This seems to mean that the computational effort to an adversary who wishes to defeat the proof-of-work system is a linear function ("51%") of the total amount of computing power in the network.  That amount of computing power definitely exists, so it is theoretically possible for some combination of actors to collude and assemble that much.  Whereas an asymptotically secure scheme—like cryptographic ones are—can in principle be tuned so that the universe might not be big enough to crack them.


Inner product with homomorphic encryption I want to do a very simple thing: Given two vectors, I want to encrypt them and do some calculation, then decrypt the result and get the inner product between both vectors. I want to do this as fast as possible for the biggest vector dimension possible.

Can you recommend any reference which may help me understand things and how to do it?

Or maybe you can even point me to some library that can do this? I found HELIB, but I don´t know if that is the best solution for my purpose. Since I have only basic knowledge in cryptography, I´ld like use it as black box as much as possible without having to put too much effort in the math behind it.

You can use these schemes instead:

“Evaluating 2-DNF Formulas on Ciphertexts”, or
“A Simple BGN-type Cryptosystem from LWE”.

These schemes enable you to do addition, a single multiplication, and more additions. For inner product, that's all you need (encrypt each item separately, multiply pairs, and add all together).

Not everything needs FHE. In any case, somewhat HE would suffice since it's just a single multiplication.


Find Points of order 2 on elliptic curve Suppose there is an elliptic curve

$E:y^2=x^3+(p-1)\cdot x\bmod{p}$

with $p>3$.

The question is: What are the points that have an order of 2?

Let $E$ an elliptic curve defined by the equation $y^2 = f(x)$ over a prime field $\mathbf F_p$ with $p>3$, with $f$ a degree $3$ polynomial.

A point $P=(x_0,y_0)$ of order $2$ is a point that satisfies $2P = \mathcal O$ where $\mathcal O$ is the neutral element of the group law also known as the infinity point. Then we have
$$
2P = \mathcal O \quad \Longleftrightarrow \quad P + P = \mathcal O \quad \Longleftrightarrow \quad P = -P,
$$
but $-P = (x_0,-y_0)$ so it means that $y_0 = - y_0$ so $y_0 = 0$. There we have it, a point of order $2$ must have its $y$-coordinate set to 0, and plugging it into the curve equation, then $x_0$ satisfies the equation
$$
f(x_0) = 0.
$$
To find all the $2$-torsion points you must find the roots of this polynomial.

Example: the curve $y^2 = x^3 + 10x + 6$ on the field $\mathbf F_{17}$ has three points of order $2$: $(1,0)$, $(2,0)$ and $(14,0)$, since we have $x^3 + 10x + 6 = (x-1)(x-2)(x+3)$.


How does ECDH arrive on a shared secret? I read a brilliant, three part article on Elliptic Curve cryptography (one, two, three).  It was able to explain Elliptic Curves to me in a way that didn't require a math degree to understand.   The crux of the article is in page two, namely, when it discussed the "dot" operation:

In the brilliant animation above (all credit goes to the original author, Nick Sullivan), the author explained that the heart of EC Crypto is that if you take any two points on the curve, A and B, and draw a line from A to B, and then continue the line you end intersecting one, and only one, other point on the curve.  You then go to the x-axis opposite (up or down) to find a third point, point C.

This is expressed in the article as:

  A dot B = C

This can continue, using the initial point and the newly acquired point as necessary:

  A dot C = D
  A dot D = E

We can continue this process an arbitrary number of times, but we'll stop after, for the sake of an example, 25 steps and end up at a point Z.
Now we know that if we started at A and applied the process above, it would take 25 total "dot" operations to get to Z.  But supposedly, this is a number that is very difficult to determine from someone if they just knew where we started (point A) and where we ended (point Z):

  It turns out that if you have two points, an initial point "dotted" with itself n times to arrive at a final point, finding out n when you only know the final point and the first point is hard. To continue our bizarro billiards metaphor, imagine that one person plays our game alone in a room for a random period of time. It is easy for him to hit the ball over and over following the rules described above. If someone walks into the room later and sees where the ball has ended up, even if they know all the rules of the game and where the ball started, they cannot determine the number of times the ball was struck to get there without running through the whole game again until the ball gets to the same point. Easy to do, hard to undo. This is the basis for a very good trapdoor function.

Now, here is my question:  How do two parties use EC and the 'dot' operation to determine a shared secret over an unsecured medium?  Effectively, how do they use A, B, Z, or 25 from the examples above to arrive at a shared secret?

For the purpose of this question, I am not concerned with how the curve is determined, I'm content with the fact that there are pre-existing curves that both parties choose to use.

Also, I am not concerned with Ephemeral variants of DH or not, at this point, knowing the basic concepts described in the article above, I just want to know what values each party start with, and what they do with those values, and what (if anything) is shared across the wire.

Let's assume that everyone agreed on some elliptic curve and a public base point $g$ somewhere on the curve.
When two parties Alice and Bob want to agree on a shared secret, they proceed as follows:

Alice chooses some random number $a$ and applies the curve operation to $g$, the public base point, $a$ times. She obtains some result $A=g^a=\underbrace{g\cdot g\cdots g}_{\text{$a$ times}}$ and shares this point across the wire with Bob.
Likewise, Bob chooses a random number $b$ and publishes $B=g^b$.
Alice takes Bob's point $B$ and applies the curve operation $a$ times to it to obtain a point $S$. That is, $S=B^a=\underbrace{B\cdot B\cdots B}_{\text{$a$ times}}$.
Bob takes Alice's point $A$ and proceeds accordingly to obtain $S'=A^b$.

At this point, the important thing to notice is that applying some operation $a$ times $b$ times is the same thing as applying some operation $b$ times $a$ times. To keep abusing the billiards metaphor: Hitting a ball $3$ times and repeating this process $5$ times is exactly the same thing as hitting a ball $5$ times and repeating this process $3$ times. In both cases, the ball gets hit $15$ times. Therefore, $S=S'$ is a shared secret!

We have yet to make plausible why $S$ is secret: An attacker only sees $A$ and $B$ and wants to find out what point would result in "mixing" the operations performed by Alice and Bob. Mathematically speaking (this is known as the Diffie-Hellman problem): Given $g^a$ and $g^b$, what is $g^{ab}$? The obvious (but perhaps not the only) way to solve this problem is to compute $a$ and $b$ and simply evaluate the desired expression (remember, hitting the ball is easy!). But computing $a$ or $b$ (solving the discrete logarithm problem) is hopefully — this is in fact an open problem — hard when they are sufficiently large, as described in the text you cited. Therefore, an attacker has (for all we know) a very hard time obtaining the shared secret $S$, and Alice and Bob can live their lives happily ever after.

As to the ephemeral "variants": There are none. The difference lies exclusively in the way the above procedure is used: "ephemeral" simply means that the private keys $a$ and $b$ are generated only for one single session and thrown away afterwards, providing forward secrecy.

Edit. As Stephen pointed out in the comments, it is actually not that easy: If Alice just naïvely applied the curve operation $a$ times, an attacker might obviously also have the computing power to conduct a brute-force search for $a$. In fact, the repeated application of the operation is performed using exponentiation by squaring, effectively obtaining the result in time $\mathcal O(\log a)$ instead of $\mathcal O(a)$. It is based on the observation that, when $a=2a_h+a_\ell$ with $a_\ell\in\{0,1\}$, then
$$g^a = (g^2)^{a_h}\cdot g^{a_\ell}\text.$$
Recursively applying this identity to compute $(g^2)^{a_h}$ until $a_h$ is zero requires a number of steps proportional to the bit length of $a$. When $a=\sum_{i=0}^ra_i2^i$ with all $a_i\in\{0,1\}$ is the binary representation of $a$, this yields the formula
$$g^a=g^{\sum_{i=0}^ra_i2^i}=\prod_{i=0}^rg^{a_i2^i}\text.$$
(Without using formulae, this means: For each $i$ where the $i$th least significant bit of $a$ is set, take $g$ and square it $i$ times. That is, set $t:=g$ and repeat the assignment $t:=t^2$, i.e. apply the curve operation to $t$ and $t$ and call the result $t$ again, $i$ times. Do this for all $i$ and combine the resulting $t$s using the curve operation.)


Partial key reveal for SHA-256 hash Let's say I have a message 0123456789abcdefghijklmnopqrstuvwxyz which gives me the SHA-256 hash 74e7e5bb9d22d6db26bf76946d40fff3ea9f0346b884fd0694920fccfad15e33.

I want to prove to someone that I know a part of the message that hash to the hash, for example xxx34567xxxxxxxxxxxxxxx is it possible to do this?
Obviously the counter party should not know what xxxxxxxxx stands for.

I'm reading the question as:

Prover knows a message (thus its SHA-256 hash, and message length), and position+length of a substring (thus the substring).
Verifier knows the hash, the substring and its position (thus length), and message length.

Prover should demonstrate knowledge of a message with such SHA-256 hash and length and with such substring at such position, without revealing more information about such message.

This is possible: we define a variant of SHA-256 with fixed message length and fixed substring at fixed position. The problem then reduces to demonstrating knowledge of input of that hash to a verifier knowing the hash, which is covered in this question.

I do not know exactly how much info must be exchanged between prover and verifier.

A concrete implementation is described by Irene Giacomelli, Jesper Madsen, Claudio Orlandi, ZKBoo: Faster Zero-Knowledge for Boolean Circuits, in proceedings of SEC'2016.


What is actual difference between POODLE and BEAST? I know that both attacks are based on the fact that the cipher used for communication is block cipher with CBC mode of operation and that is vulnerable because of predictable IV. Furthermore the original paper of POODLE claims that

  "Unlike with the BEAST [BEAST] and Lucky 13 [Lucky13] attacks, there is no reasonable
  workaround."

But openssl library seems to have implemented some mitigation technique known as 0/n split(to be fair I did not understand how that works either) and that seems to mitigate POODLE as well as BEAST. Then why research paper claims so?

BEAST was indeed an attack on CBC mode with predictable (in fact known) IV in SSL3 and TLS1.0, because those protocols used the last block of the previous record, which (usually) has already been sent and seen by the adversary, as the IV for the next record.

Record splitting blocks this by encrypting a (mostly) fixed stub record (at most one byte of data, plus HMAC and padding) using the known IV, producing quasi-random ciphertext, and in the same transmission sending (nearly) all the data in a second record using as IV the last block of the first record which is now not predictable. OpenSSL did 0/n splitting back in 2002 in response to an observation of this flaw by Rogaway, but it was widely disabled for interoperability; pretty much everybody else did 1/n splitting rapidly (weeks or months) in response to BEAST in 2011. The former is described adjacent to the document you linked at https://www.openssl.org/~bodo/tls-cbc.txt

See also https://security.stackexchange.com/questions/17080/is-there-a-way-to-mitigate-beast-without-disabling-aes-completely
POODLE is not an attack on IV at all; it is a padding oracle attack on the padding used in SSL3 (and it turned out some debatably defective TLS1.0 implementations also), hence the acronym Padding Oracle On Downgraded Legacy Encryption. Because POODLE has nothing to do with the IV, predictable or otherwise, fixing the IV has no effect on it.

See canonical (and ursine) https://security.stackexchange.com/questions/70719/ssl3-poodle-vulnerability/ and perhaps (mine, but nearer) How does padding oracle attack work with bytes larger than possible length?