Using beginning of TLS ecnrypted data to reveal secret I have the following question about TLS security:

Assume TLS-PSK protected HTTP with AES256-CBC cipher.
When a TLS connection is established, client sends some encrypted data, where the
plaintext is well known to an attacker.

For example, it can be a HTTP request, like:

GET /some_resource HTTP/1.1
...

Can an attacker use intercepted ciphertext and known plaintext it to reveal the secret key?

Does TLS have any features to protect from that?

This question boils down to, "Are there known-plaintext attacks against AES-256-CBC?" The answer is: No, no such attacks better than brute force are known. This would constitute a catastrophic break in AES-256-CBC, and any cipher broken in such a way would be abandoned rapidly.


ROT encryption with hash functions I am not trying to create my own encryption (I am just interested in the math and possibility of this form of "encryption"). I apoligize if this post does not fit in, it is my first time posting.

A Caesar cipher is probably the most basic form of encryption, but what if we were to step it up?

We take a password key
We hash it through a SHA256 algorithm and save the result
We hash the result multiple times saving the result each time
We take all of the results and stack them (using simple numbers for example)

123 < Hash
 321 < Hash 2
 221 < Hash 3
We add up the values of each column

1  2  3 < Hash 1
  3  2  1 < Hash 2
  2  2  1 < Hash 3
 (6)(6)(5) < Final result
We apply the resulting numbers to our text to be encrypted through a Caesar cipher
When we get to the last digit in the ROT, we continue steps 3-6 untill complete

Decryption would be as simple as entering a password to hash over and over and undo the Caesar cipher

What is the practicality of this; does it exist/what would be potential flaws?

Here is an example of this encryption in python. Run the program and you will see what I am trying to explain.

What you are describing is a strange version of OFB mode, using a hash function instead of a block cipher and modular addition instead of XOR to combine the data with the keystream. The algorithm you describe appears vulnerable to known plaintext attacks. A simple tweak to make it more similar to true OFB mode would improve security. OFB mode is a stream cipher mode:

\begin{align*}
O_i = E_K(O_{i-1}) \quad\text{where}\quad O_0 = IV
\end{align*}

The keystream is $O$, so encryption and decryption is implemented as in any stream cipher:

\begin{align*}
C_i &= P_i \oplus O_i\\
P_i &= C_i \oplus O_i
\end{align*}

This technique can be visualized:

The block cipher, $E$, can be replaced with any keyed hash function. The hash function must be keyed and the initial input must be an IV, not a key, otherwise it is vulnerable to a known plaintext attack where an attacker who can derive one of the outputs can use it to calculate the rest of the keystream. Your current construction is $O_i = H(O_{i-1})$ where $O_0 = H(K)$, with multiple blocks of keystream $O$ being used to encrypt a single block of plaintext. If I understand this correctly, this does not resist known plaintext attacks. Instead, you need to use a keyed hash and the first input should be an IV. One of the most common keyed hash constructions is an HMAC:

\begin{align*}
\operatorname{HMAC}_K(m) = H((K \oplus \mathrm{opad}) \mathbin\| H((K \oplus \mathrm{ipad}) \mathbin\| m))
\end{align*}

The $\oplus$ represents the XOR operation. Any operation that can be reversed with the same input can be used for this purpose, not just XOR. In your scenario, a Caesar cipher functions as modular addition, so if I understand what you are describing correctly, it should have similar security to OFB mode, including its pitfalls (short permutation cycles, for example), as long as you replace your hash function with a proper keyed hash like an HMAC.


Proving security for Secure Multiparty Computation with malicious adversaries In the case of malicious adversaries, while creating a simulator for an attacker in the real world what are the algorithms that this simulator has access to and why?

For eg. I've seen simulators that use the adversary in the real world and also rewind them.

I do not understand what powers are given to the simulator and why.

I would like to provide a short answer, please see Lindell's tutorial for a comprehensive explanation.

As with the semi-honest model, the simulator in the malicious model also needs to simulate the real-world protocol execution (where some parties are controlled by an adversary). The simulator has access to the ideal functionality and an adversary (which is assumed to exist when constructing the simulator). The simulator can treat the adversary as a black-box algorithm and control its inputs and randomness tape. So, the simulator can rewind the adversary back to a particular step (where it needs some input to continue) and then feed it with a different input. However, simulation in the malicious model is much harder than that in the semi-honest model, mainly because we do not know what inputs the adversary is actually using even if we know what inputs are given to them.


Can I decrypt the message having it encrypted with different keys? I have some encrypted binary data I want to decrypt. I know nothing about it, but I can get it encrypted with as many different (random, unknown) symmetric keys as I want. The keys are long enough to not get repeated. Something like this:

$A_1 = Data ⊕ Key_1\\
A_2 = Data ⊕ Key_2\\
A_3 = Data ⊕ Key_3\\
…\\
A_n = Data ⊕ Key_n$

Is it possible to get $Data$ just having the $A$s?

Thanks

If the keys are at least as long as the data (which is confirmed in the comments), and the keys are chosen randomly and independent of each other, no there is no way to get the data. Even if you had infinitely many encryptions.

This is because this type of encryption, called the one time pad, is perfectly secure.


How to factor an RSA256 public key with YAFU? (Layman's terms please, I'm just a kid stuck on a puzzle)

I'm trying to factor the following RSA256 public key to find the corresponding private key:

MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAIl47p5SrV3uMTsUAbwE0E+j+QynAY/CVq/Gf8IAOQy7AgMBAAE=

I got as far as downloading a YAFU factorization program found here, which I was told is capable of factoring such a key in 103 seconds on a core i7. This program works great for factoring base 10 numbers, but I have no idea how to use it on a  RSA key. Any help would be hugely appreciated. Thanks!

There are various ways of doing this. Let's assume you're using Python.

Start by installing PyCrypto. This includes a lot of useful tools.
You need to convert the raw base64 string into a readable RSA key file. This is easily done:

-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAIl47p5SrV3uMTsUAbwE0E+j+QynAY/C
Vq/Gf8IAOQy7AgMBAAE=
-----END PUBLIC KEY-----

Save this to a file called, for example, rsa256.pub.
Import this key into Python and extract the values of $n$ and $e$:

from Crypto.PublicKey import RSA
key = RSA.importKey(open('rsa256.pub').read())
print key.n, key.e

Now factorize $n$. YAFU sounds perfect for the job. (I use msieve, which also works well.) On a decent computer, it should only take a few minutes to break a 256-bit modulus. This will give you two factors. Call the larger one $p$ and the smaller one $q$.
Back in Python, you need to run a bit of code to calculate the decryption exponent $d$. You should then have sufficient information to generate a private key:

def egcd(a, b):
    """Extended Euclidean algorithm"""
    """https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"""
    x,y,u,v = 0,1,1,0
    while a != 0:
        q, r = b // a, b % a
        m, n = x - u * q, y - v * q
        b,a,x,y,u,v = a,r,u,v,m,n
    return b, x, y

def modinv(e, m):
    """Modular multiplicative inverse"""
    """https://en.wikipedia.org/wiki/Modular_multiplicative_inverse"""
    g, x, y = egcd(e, m)
    if g != 1:
        return None
    else:
        return x % m

def pqe2rsa(p, q, e):
    """Generate an RSA private key from p, q and e"""
    from Crypto.PublicKey import RSA
    n = p * q
    phi = (p - 1) * (q - 1)
    d = modinv(e, phi)
    key_params = (long(n), long(e), long(d), long(p), long(q))
    priv_key = RSA.construct(key_params)
    print priv_key.exportKey()

Call pqe2rsa() with the values of $p$ and $q$ from step 4 and the value of $e$ from step 3, and you should get a private key.


IV's for different AES encryption modes I wanted to know if my understanding is correct!
I have been reading up on aes encryption and modes(specifically CTR and CBC) and it took me sometime to understand the concept of IV.
If the IV is generated randomly then:

In CBC mode typically IV is prepended or appended after the encryption,So the first block of the cipher text is decrypted using this first block of data recieved which is the IV and from there on the previous cipher block is the IV for the next block.

I am not sure about the practice in CTR mode but there is a counter(or nonce) that increments the IV for each block for decryption adn encryption.

If the IV is generated value then well both parties need to agree on how it is generated.
And using a constant IV is not really recommended to use a fixed IV for any mode.

I also want to know, what other standard practices are in use to communicate the IV in between two parties in different AES modes?

For CBC mode, the IV can be generated in any manner where it would be unpredictable to an attacker from one message to the next. In practice that means a random number generator of some kind. Since the block size is 128-bits, the probability of IV repeat before the key expiration is negligible. The CBC IV is visible to an attacker viewing your ciphertext; as you said, it is attached some how.

There does not need to be any agreement on both ends as to the method of generating it. Most implementations I know of prefix the ciphertext with the IV.

For CTR mode it is a different story. The IV is the combination of Nonce and Counter. There needs to be strict agreement on both sides how they are combined and incremented, or the other party will not be able to decrypt. Additionally if the same key is used by both parties, they need to make sure there is no Nonce reuse between the 2. This can be achieved by forcing one party to always have a specific bit of the Nonce set to 0, and the other party set that bit to 1, such as the MSB. The better option is to have 2 different keys. Since CTR mode turns the block cipher into a stream cipher, IV reuse in CTR mode is catastrophic. There is no requirement that the Nonce be unpredictable, and can be a simple message counter.

The nonce is the only part of the CTR IV that is transmitted with the message, and once again it is visible to an attacker. Most implementations I know of prefix the ciphertext with the Nonce, and the block counter for the message starts at 0, except in the case of AES-GCM.


Why is TLS SRP verifier based on user name? I don't understand why TLS SRP (or SRP in general) includes the user name in verifier calculation, given that user name is basically public.

From spec RFC 5054 $x$, which is then used to calculate verifier, is calculated as follows:

x = SHA1(s | SHA1(I | ":" | P))

I thought about removing 'I' to facilitate changing of user names(verifier won't have to be recalculated). Then $x$ will be:

x = SHA1(s | SHA1(P))

However I'm not sure if it will have any negative impact on the protocol. Will that change decrease security?

One of the design goals of SRP is that it should be a zero-knowledge authentication protocol.  This is to say, even the legitimate server should not be able to learn anything about the user's password (other than what it could learn using a generic brute force attack on the verifier).

SRP also assumes that the user may not be able to remember anything except their username and password.  In particular, even though the user may choose the salt when they first compute their verifier, that salt is stored on the server and is sent back to the user by the server whenever the user wants to authenticate.

If the username was not included in the verifier calculation, a malicious or compromised server could try to learn whether user Alice had the same password as user Bob by sending Bob's salt to Alice when she tries to authenticate and seeing if the authentication (using Bob's verifier) still succeeds.  Including the username in the verifier prevents this potential information leak.

Admittedly, this is a fairly minor leak, and probably not of much concern in practice.  Still, it does violate the intended zero-knowledge property of SRP.

Ps. While looking at the SRP documentation to see if it says anything about this, I noticed something curious: the original 1998 paper defining SRP-3 doesn't seem to say anything about the username being included in the verifier calculation.  Indeed, the protocol specification in section 3.2.2 simply says that:

  "To establish a password $P$ with Steve, Carol picks a random salt $s$, and computes: $$x = H(s, P)$$ $$v = g^x$$

However, the SRP-6 paper starts off with:

  "The original protocol, sometimes referred to as "SRP-3" for historical reasons and specified in [4], operates in a group defined by a large safe prime $p$ and a primitive root $g$. Reviewing briefly, the server computes its verifier value $v$ for a user identity $I$ as follows: $$x = H(s, I, P)$$ $$v = g^x$$

The reference "[4]" in the SRP-6 paper is not actually to the earlier paper, but to RFC 2945, which claims to describe the same protocol as the SRP-3 paper but does include the username in the calculation.  So apparently this change was quietly made at some point between the publication of the SRP-3 paper in 1998 and its standardization as RFC 2945 in 2000.


Is the Representation Problem hard on elliptic curves? The RP in ECC would be to find $a_1,\ldots,a_n$ (integers) given $P$ and $Q_1,\ldots,Q_n$ (points in the EC) such that  $P = a_1 \cdot Q_1 + \ldots + a_n \cdot Q_n$.

Is it hard when DH-like assumption holds in the EC?
Is is hard in secp256k1 or Curve25519?

If RP is easy, then so is discrete logarithm.

Assume that you have a way to easily solve the RP for a given $n$. Now I give you $G$ and $P$ on the curve (of size $q$), and I want you to find $x$ such that $P = xG$. What you do is the following: you generate random integers $r_1, r_2, \cdots, r_n \mod q$, and compute $Q_i = r_iG$ for all $i$ from $1$ to $n$. Then you solve RP for P relatively to those $Q_i$, yielding the $a_i$. You then get $x = a_1r_1 + a_2r_2 + \cdots + a_nr_n \mod q$.

Since discrete logarithm is hard in elliptic curves, so must be RP.


Is a random circuit likely to compute a one-way function? I remember reading somewhere that (under certain reasonable assumptions) a Boolean circuit with many inputs and outputs (assume equal number for now) chosen at random will be a one-way function with high probability.  Is this true?

The claim that you remember is to good to be true. It is yet unknown (because the question P ?= NP is still open) whether there are one-way functions. If the claim you remember was true, it would prove the existence of one-way functions.

P.S. While P = NP excludes the existence of one-way functions, even with P != NP the existence of one-way functions is still an open problem.


Self-correcting encryption. What are the essential elements? Optical discs are prone to damage, and for this reason, they usually store data encoded with an error correcting code.
While day-to-day use for optical storage media has diminished in recent years, they continue to be used for distribution of movies and TV shows, given they have special value to collectors. In such applications disc content is usually encrypted to protect copyright, which begs the question, what are the requirements for their decryption to be successful?
Now let me formulate a scheme, with layers consisting of error-correcting codes and ciphers.
Before data is burned onto a disc, it goes through 3 layers:

Inner-layer error correcting code,

Encryption,

Outer-layer error correcting code.

The tricky part is encryption. It seems that only a stream cipher can be used, otherwise the inner-layer error correcting code will be meaningless when the decryption fails. As such, deterministic authenticated encryption and key-wrapping ciphers cannot be used here. So a stream cipher must be used, and nonce must receive extra protection against potential errors in the outer-layer error correcting code.
My question is: if there's an inner-layer error correcting code, will it be able to work without an encryption algorithm based on a stream cipher? How do DRM-protected discs usually protect its contents from theft and physical damages?

if there's an inner-layer error correcting code, will it be able to work without an encryption algorithm based on a stream cipher?

Depends on how the inner error correcting code works; what you want is an encryption method that does not radically increase the 'size' of any ciphertext errors (where 'size' is what's relevant to the error correcting code), given the likely ciphertext errors (and I believe that on Optical disks, burst errors are far more common than random unrelated bit flips).  If it is (for example) a Reed Solomon code, that means that it would not increase the number of incorrect (modified) symbols; there are alternatives (other than stream ciphers) with this property.
However, that does beg the question: "what do you hope to gain with this structure?"  Wouldn't this structure at least as good:

Encryption

"Inner" error correcting code

"Outer" error correcting code

(or combine "inner" and "outer" if that makes more sense).  That would (to me) appear to be at least as good with dealing with errors (and you don't have to select your encryption method with the error correcting code in mind)


How to compute the inverse of a polynomial under $GF(2^8)$? It's well known that AES cryptography algorithm uses Galois Field $GF(2^8)$ multiplication to process the step MixColumn, and each column of the 4x4 matrix on encrypting should multiply the polynomial $3X^3 + X^2 + X + 2$ which is usually notated as an array $\{\tt 0x03, 0x01, 0x01, 0x02\}$, while on decrypting, the matrix should multiply the inverse of the polynominal mentioned above, namely $\texttt{0x0B}X^3 + \texttt{0x0D}X^2 + \texttt{0x09}X + \texttt{0x0E}$ which can also notated as an array $\{\tt 0x0B, 0x0D, 0x09, 0x0E\}$.

Now I wonder If only one polynomial is known, e.g. $\{\tt 0x03, 0x01, 0x01, 0x02\}$, how can I compute its inverse mod $(X^4 + 1)$, namely $\{\tt 0x0B, 0x0D, 0x09, 0x0E\}$, and vice versa.

The classic generic algorithm for computing modular inverses is the Extended Euclidean Algorithm. The algorithm is primarily defined for integers, but in fact it works for all rings where you can define a notion of Euclidean division (i.e. "Euclidean domains"). In particular it works with polynomials whose coefficients are in any field.

Let $K$ be a field. In the case of AES, this is $\mathbb{F}_2^8$, the finite field with 256 elements, but this does not actually matter here. $K[X]$ is then the ring of polynomials with coefficients in $K$. Given two such polynomials $A$ and $B$, you can find polynomials $Q$ and $R$ such that $A = BQ + R$, and the degree of $R$ (the largest power of $X$ for which the corresponding coefficient of $R$ is non-zero) is strictly less than the degree of $B$. This is easily computed in about the same way you would compute a division of integers; in fact it is easier because there is no carry to propagate between coefficients.

The magic part of it is that the $Q$ and $R$ polynomials are unique; i.e. for two polynomials $A$ and $B$, there is only one pair of polynomials $(Q,R)$ that matches the conditions above. Thus, the Euclidean division of polynomials is well defined, and the Extended Euclidean algorithm works.

In practice, the Extended Euclidean Algorithm is about finding the Greatest Common Divisor. In the context of polynomials, "greatest" means "of largest degree". Note that this GCD is defined only up to a multiplicative constant; it is often taken as convention that the GCD should have its largest non-zero coefficient equal to 1 (you can always arrange for that, because if polynomial $B$ divides polynomial $A$, then $tB$ also divides $A$ for all non-zero field elements $t$).

So if you have a polynomial $A$ and want to inverse it modulo $B = X^4+1$, then you run the Extended Euclidean Algorithm to obtain polynomials $U$, $V$ and $G$ such that $G$ is the GCD of $A$ and $B$, and $AU+BV = G$.

If $G$ has degree 0 (i.e. it is the constant $1$), then $A$ is invertible modulo $B$, and its inverse is $U$.

If $G$ has a non-zero degree, then this means that $A$ and $B$ can both be divided by that non-trivial polynomial, and there is no solution: $A$ is then not invertible modulo $B$.

Note that $X^4+1$ is not irreducible over $\mathbb{F}_2^8$; it is equal to $(X+1)^4$. It follows that a polynomial $P$ of degree at most 3 in $\mathbb{F}_2^8$ is invertible modulo $X^4+1$ if and only $P$ is not divisible by $X+1$, i.e. $P(1) \neq 0$. For $P = 3·X^3+X^2+X+2$ (I am calling "$3$" what the AES specification denotes 0x03), you have $P(1) = 3 + 1 + 1 + 2 = 1$ (remember, we are working in $\mathbb{F}_2^8$, so addition is XOR), so that polynomial $P$ is indeed invertible.

Another, completely different way of computing inverses is with modular exponentiation. The polynomials which are invertible modulo some given polynomial $B$ form a multiplicative group. If that group has order $e$, then the inverse of any invertible polynomial $A$ modulo $B$ is necessarily $A^{e-1} \pmod B$. In the case of $B = X^4+1$, the invertible polynomial modulo $B$ are all the polynomials $P$ such that $P(1) \neq 0$, so $e = 255·256^3 = 4278190080$ (this is easily seen in the following way: you can choose three coefficient arbitrarily, but for the fourth coefficient, you must avoid the one value that would make $P(1) = 0$). Therefore, to compute the inverse of a given polynomial $A$ modulo $X^4+1$, you "just" have to compute $A^{4278190079} \pmod {X^4+1}$, which can be done with a square-and-multiple algorithm.

That method is less efficient than the Extended Euclidean Algorithm, but possibly simpler to implement.


Questions about Key Derivation Functions My understanding is that a KDF is a function that takes a master secret and generates multiple keys. It is secure as long as the keys are "independent". If this is true, the following definition would generate a secure KDF, right?

  Assuming we have access to a completely random function, $R:
\mathcal{K} \rightarrow \mathcal{K}$, we can define  a $KDF :
\mathcal{K} \rightarrow \mathcal{K}^n$ that on input $S \in \mathcal{K}$ performs
  the following.
  $$K_1 = R(S \oplus 1)$$ $$K_2 = R(S \oplus 2)$$ $$\vdots$$ $$K_n = R(S
\oplus n)$$
  Output $(K_1, K_2, ..., K_n).$

Now of course, we cannot construct random functions so what we do instead is to replace $R$ by a pseudorandom function that no "efficient" adversary can distinguish from random.

Questions:

Does this mean that replacing $R$ by, e.g. $AES(k, \cdot)$, where $k$ is fixed would also give a secure KDF? Does $k$ need to be chosen with some care or can it be any value? Would $AES(\cdot, m)$ for a fixed $m$ be equivalent?
Does this mean that replacing $R$ by any secure hash function would also give a secure KDF? If that is the case, why does some KDF-suggestions use HMAC instead? Is this only to get a larger "security margin", and to be less depending on the security of the used hash function? Would replacing XOR above with concatenation (which is possible for the hash-function case but not for block cipher case) affect security?
If I want to implement a secure KDF, and already have access to AES, SHA1-512, and HMAC, how would I do it such that it is simple but yet secure?

Let's start with a general secure KDF construction, as follows. Let $F(k,x) \rightarrow \{0,1\}^n$ be a secure PRF. Then choose $L$ such that $L \times n$ provides as many output bits as you need for all of your generated keys. Let $S$ be your original secret key/entropy. Generate the following string:

$KDF(S,N,L) := F(S, C || 0) || F(S, N || 1) || ... || F(S, N || L)$

where N is a unique value per application that calls the KDF. In the case that you are generating $n$ bit keys, you would simply assign each key $K_i := F(S, N || i)$.

This is similar to your construction, but distinctly different. In your construction, $R$ is fixed across all calls, whereas the PRF above chooses a different random function for each entropy input. In fact, you are essentially trying to emulate the behavior of the PRF by using $R$ and $S$ prefixed to all the inputs. However, I don't know if $R(S || X)$ is as secure as $PRF(S,X)$, and I wouldn't assume that without some proof. At any rate, I don't think we even have any modern algorithm candidates for something like $R$ aside from taking a $PRF(k,x)$ and fixing $k$ to be some constant.

One advantage of the constructed $KDF$ above is that it is more resistant to bad input, namely it will provide unique keys even if the input is improperly provided. Should the same entropy be accidentally given to multiple processes (perhaps due to entropy failure), you still guarantee unique keys are generated in each process due to the $N$ value. And concatenation is safer than XOR when it comes to combining a fixed value with a counter. This is because with XOR, incrementing the fixed value and calling again may create the same value after the XOR with the counter. Eg, fixed value 0x71 $\oplus$ counter value 1 yields 70, as does fixed value 0x72 $\oplus$ counter value 2. In such a case, you'd generate duplicate keys.

1) $AES(k,\cdot)$ can be used as a PRF that outputs 128 bits. (This is the premise behind the counter mode of encryption using AES.) Here, you would use $S$ as your key.

2) Conceptually, hash functions kind of look like random functions, but it is vital to understand that they are not. In cryptography theory, hashes do not have the same constraints as truly pseudo random functions (PRFs). For example, it is entirely possible that a theoretically secure hash function could leak information about the plaintext. In practice I doubt we would like a hash function that did, but nevertheless hash functions are not to be treated as random functions. In contrast, HMAC actually is a PRF, and it is conveniently built using hashes. But the construction of HMAC has advantages over plain hashes of keys concatenated with plaintext, as the latter have very concrete vulnerabilities that arise from the very fact that hashes do not have the same criteria as random functions.

3) You can use HMAC to create a KDF: Have you seen PKDF2? The implementation is fairly simple given HMAC. Or even HKDF, which is yet simpler, but I would recommend PBKDF2. The construction I outlined in the beginning using AES as the PRF would also work.


Why are obfuscators generally defined to be probabilistic algorithms, rather than deterministic ones? One possible explanation is, randomness is not going to hurt you, so might as well use it. Also, if we are hoping to prove impossibility, it only makes the result stronger.

One other explanation is if the obfuscators are defined to be deterministic, then to satisfy the strong virtual black-box definition (and the weaker indistinguishability obfuscation definition), it should be the case that all functionally equivalent circuits (that are of similar sizes) must be obfuscated to the same circuit, and this is difficult.

But, what if we are considering a class of circuits where no two circuits in the class are functionally the same? For example, a class of point circuits (where each circuit in the class evaluates to 1 on a specific point that is hard-wired in that circuit, and evaluates to 0 on all other points). Does it make sense to think of deterministic obfuscation in this case?

Let's consider the notion of IO (indistinguishability obfuscation). Informally, the definition states that for every two circuits $C_1$ and $C_2$ such that $C_1(x)=C_2(x)$ for every $x$, it holds that $IO(C_1)$ is computationally indistinguishable from $IO(C_2)$. That is, a distinguisher knowing $C_1$ and $C_2$ and given an obfuscation of one of them cannot guess which with probability greater than $1/2$.

Now, assume for a moment that $IO$ is a deterministic algorithm. In addition, assume that $IO$ does not map all equivalent $C_1,C_2$ to the same concrete output (if it could do this, then we would have an efficient way of determining that circuits compute the same function, which is co-NP complete). Then, the distinguisher could simply compute $IO(C_1)$ and $IO(C_2)$ and compare to the obfuscated program that it received. With this strategy it knows which circuit was obfuscated with probability 1. Thus, $IO$ cannot be deterministic.


What is p.p.t simulator? I was reading research paper Reusable Garbled circuit in which i read the term "p.p.t Simulator" and p.p.t Algorithm. I know about Probablistic Polynomial Time(p.p.t) Algorithm. Kindly someone tell me what is Probablistic Polynomial Time Simulator

A PPT simulator is really just a PPT algorithm. So if you know what a PPT algorithm is then you know what a PPT simulator is as well.

The term simulator is used in many contexts in cryptography, but typically they are PPT algorithms that are supposed to produce output according to some distribution simulating the output distributions of one or more parties in some protocol.


HMAC vs CMAC, which is faster? I want to know which is faster-HMAC or CMAC.I know CMAC is based on block cipher encryption,where output of each block is X-OR with the next plain text block. If security is not a concern,which will be faster to use?

Which MAC algorithm is faster - CBC based MAC's or HMAC - depends completely on which ciphers and hashes are used. Furthermore, it depends on the runtime environment that contains the hash and cipher implementations.

With regard to the leading CPU architecture for PC's, there are the Intel whitepapers. Both AES and SHA-2 performance can be enhanced using CPU constructions. See for AES the AES-NI page on Wikipedia. Likewise, the Intel SHA extensions for later CPU's can also be found there. Both are also available on later AMD processors because of the cross licensing agreements between those firms.

Obviously not all runtimes do get direct support for these constructions. At that point it is very much dependent on the implementation. If you can get away with using HMAC-SHA-1 then it is likely that SHA-1 outperforms any other MAC algorithm (besides MD5, which is also secure for smaller HMAC output sizes). In general you're best off to test which specific algorithms perform best on a platform.

OpenSSL CLI has a speed option that can be utilized, for instance use:

openssl speed sha512 aes-256-cbc

to see the speed of the CPU with regards to bytes processed per second (I'm always pretty stumped when I see them on my lowly mobile i7 CPU).


Decoding Base64 message encoded with a key. I only know the ciphertext and code import binascii
import re
import base64

ptext = input("Enter Plaintext\n\n\n")
print(ptext)

key = input("Enter Key\n\n\n")
print(key)

ptext01 = ""
key01 = ""

for c in range(0, len(ptext)):
    ptext01 = ptext01 + ("%x" % ord(ptext[c]))

for c in range(0, len(key)):
    key01 = key01 + ("%x" % ord(key[c]))

i = 0
j = 0
s = ""

while j < (len(ptext01)):
    while i < (len(key01)):
        if len(str(hex(int(key01[i:][:+2], 16) ^ int(ptext01[j:][:+2], 16)))[2:]) == 1:
            s = s + "0" + str(hex(int(key01[i:][:+2], 16) ^ int(ptext01[j:][:+2], 16)))[2:]
        else:
            s = s + (hex(int(key01[i:][:+2], 16) ^ int(ptext01[j:][:+2], 16)))[2:]
        i += 2
        j += 2
        if j >= len(ptext01):
            break
    i = 0

result= int(s, 16)
encodedBytes = base64.b64encode(str(result).encode("utf-8"))
encodedStr = str(encodedBytes, "utf-8")

print(encodedStr)

This is the code used to cipher the text, and this is the ciphertext:

  NDcyMDI5MDYwMzI3MjM5NDgxNjc0NTgxMDI5OTYxMzIxMDQ1MjMxOTA3OTI1MDg5NDU3MTEyNTc2ODcyMzAxMzQ2NTAzMDMzNTgzMzc5MDMwNzYyODQ2NTU2NjQ2MTQ4MzQ1NjAwODQwOTgyNTc3MzM0NDk2Mjk1MTM2MjA5OTEzMTc5ODUwNzg2NzQ3MTU3NDc5MjQ4OTc4MDk0NDQ1Njk4Mzc1ODIxNDI5NjkwNDQ5NzAyMDIwMjUyMzIyMTY2MTI0MzM1MDc3MTc1MDI2OTcwNzMzMDI4NjI4Mjg0OTcxNzA3Nzc4MDY5NDI4NzIzODQxNzM3MzE1NTgxMDA5MjIzMzQyODQ2MDAwMTY1OTU4NzA1MDM3Mjg0MzYxMzQyOTMzNDA2MTMzMTA4OTkxNDg3MTQ2Mjk1ODM0NTI1MDEzOTU5NDgwNzg5ODMyMDYwMTcwMzQ3NTk1NjQyNjQzOTgzOTAzODQzMTAzMDQ4Nzg0ODE1MTc2MzQwNTQxOTUwMzI0MDM2MTg2NDg2OTk4MDY5NDExNzI0OTQ2NDQ0MTU5ODMzNTczMTM2NzgwMzA1NjQwOTk0MTM1MTAyMjAzNTc5MTE5MzQxNzAwNTgxMDc3MDM5Mjc1MjM2OTE2NDYxOTEzMjI3NjgzNTIwMzU0MTA3MzY0ODY5NTE2MTY3NTMzNDIxMjQ0MTYxNzU4NzUzMTkzOTkwMzgwOTYxMTMzNzk2NTA1NDc3MTEyMDc2NzQ4NzAxMDYyNzI1MDUyNzkyMzk2MTMwNDg2NTc0NzU1MzI1NDkzOTUyODIwMTE0NzY3MjgwOTgxMTU3MDAxMjQ3MDU2OTA1NDcxMjUxODQ4OTA2NDIyMDUxNzQwNTI0Mzg5NjExNDM2Mzg0NTk4MDEzNzQ4Mjc5NTYwNTc3OTM2MzM1Nzc2NTI0MTMxNDEyNjEwNzc5MzI1Mjk0NjU4Mjc1NzU5Mzc1OTQyOTgwNTk0MTMzMjExMDc5NzQwNTQ1OTMxMDIwNTg1ODMyOTkyODEzNzczNzcxNjUyMzIyODQwNTIwOTk2ODYyNDQ3NjAzMzIwMjM3MTY3MzcxMTA5NTY1MzM2ODY3OTI4NDE0OTkyNjk1NjkyODU5NDUwOTQ2NTgxOTA2Nzc1ODczOTMzNzgwMDM5OTE=

I have briefly looked at the code. It is not well readable, but it looks like it is Vigenère cipher. It seems to operate on Unicode values of the characters, but it probably does not expect the Unicode value to be over 255 or lower than 16, so it can have troubles with some unicode characters. Finally, it is encoded to base64 in order to produce ASCII characters.

So, you can use known cryptanalysis for Vigenère cipher. There are probably also some tools, but you will likely need to adjust the input.


Username and Password: How does it work? Suppose a client (Alice) goes to an HTTPS website (Bob) over TLS 1.2.

Alice sends Client Hello with some random number $r_a$.
Bob sends Server Hello with another random number $r_b$.
Suppose they settle on some cipher suite (e.g. RSA, DHE, AES, and SHA1)
Bob sends server certificate
Bob signs and sends server key exchange ($g^b$ in Diffie-Hellman)
(Bob does not request client certificate, and client does not have it.)
Alice sends client key exchange ($g^a$ in Diffie Hellman) (no signing).
Now both share "pre-master secret", namely ($g^{ab}, r_a, r_b$)
Next, for key derivation, they both use pseudorandom function (PRF) to generate from the pre-master secret the following symmetric keys:

client write key
server write key
client MAC key
server MAC key
client write IV (for use in client AES cipher)
server write IV (for use in server AES cipher)

Alice sends Change Cipher Spec and an encrypted Finished containing MAC of all previous client handshake messages.
Bob sends Change Cipher Spec and an encrypted Finished containing MAC of all previous server handshake messages.
They exchange some encrypted application data.

Suppose now Alice starts signing in with her username and password. What will happen next? Will they just scrap all the previously negotiated keys and switch to TLS-PSK with Password-Authenticated Key Agreement or Password-Based Key Derivation?  Could you please describe how client and server use username and password? What are the steps and algorithms used in this?

"Will they just scrap all the previously negotiated keys and switch to TLS-PSK with

Password-Authenticated Key Agreement or Password-Based Key Derivation?"

No.

"What will happen next?"

"Could you please describe how client and server use username and password?"

"What are the steps and algorithms used in this?"

The server will look up the username's salt, hash the password with it, and then compare

the result to the stored password has.  If they are equal, then authentication succeeds,

else authentication fails.  The algorithms used in this are PBKDF2,bcrypt,scrypt.


Montgomery Multiplication with CRT I am attempting to understand how to use Montgomery multiplication in an RSA private key operation: $X \equiv a^{e} \pmod{n}$ where $a$ is the message, $e$ is the exponent, $n$ is the modulus.
Using the algorithm from Montgomery Reduction (with $r=2^k$, where $k$ is the bit length of modulus $n$):
ModExp(a; e; n) { n is an odd number }
Step 1. Compute n' using the extended Euclid algorithm.
Step 2. a_hat := a*r (mod n)
Step 3. x_hat := 1*r (mod n)
Step 4. for i = k-1 down to 0 do
Step 5.   x_hat := MonPro(x_hat; x_hat)
Step 6.   if e(i) = 1 then x_hat := MonPro(a_hat; x_hat)
Step 7. x := MonPro(x_hat; 1)
Step 8. return x

MonPro(a_hat;b_hat)
Step 1. t := a_hat*b_hat
Step 2. m := t*n' (mod r)
Step 3. u := (t + m*n)/r
Step 4. if u >= n then return u-n else return u

Now, the modulus $n$ will always be odd in RSA since it is generated from primes, which satisfies the first requirement. Also, from what I understand, in order for Montgomery form to be possible, the size of the base $a$ must be $a < n$. Fortunately, in RSA, this also holds true as the message/signature can't be longer than the modulus.
However, here's where I'm getting stuck. I am adding in hardware acceleration to a preexisting RSA library (mbedTLS) by replacing the modular exponentiations with an accelerated version. It's working great, so long as it's not using the Chinese Remainder Theorem. I don't entirely grasp CRT yet, but I understand that it allows us to perform faster decryption by splitting the message up into two operations and shrinking the modulus size:
$$ m_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \bmod p-1}) \bmod p $$
$$ m_2 = (M^d \bmod N) \bmod q = ((M \bmod q)^{d \bmod q-1}) \bmod q $$
Taken from: Chinese Remainder Theorem and RSA
The issue is, the message length is now longer than the modulus $p$ and $q$. So now, it would violate the requirement for Montgomery form that in $(aR)*mod(N)$, $a$ must be $a < N$.
I've searched all over for a method of doing Montgomery modular exponentiation in the case that the $a > N$, but they all state that the input $a$ is smaller than $N$. I can't seem to wrap my head around how you would perform a modexp using the Montgomery form with a larger input size than the modulus.
I was thinking maybe you could chunk $a$ into binary groups of $bitlen(N)$ with some sort of carry into the next group, but I can't figure out how you would mix in the inner loop that does the squaring. Would it be possible to modify it so that it becomes:
modexp(a[0:len(n)], e, n) ... modexp(a[len(n):len(a)], e, n)

And somehow combine those into an output that would be of len(n)? I'm really lost in understanding the mathematics behind it.

The issue is, the message length is now longer than the modulus $p$ and $q$

That's not true.  In the $p$ track, you are raising $M \bmod p$ to the power $d \bmod p-1$; we have $M \bmod p < p$; that is, the value we are exponentiating is less that $p$, as results by Montomery multiplication.  In the same way, the $q$ track also satisfies the requirements on that side, and so everything works.


How DES/AES can guarantee by feeding different secret keys, the encrypted outputs are different? I am learning the meet-in-the-middle on DES attack. I understood the basic logic behind how it is performed; however, one further question is: why can we guarantee to find one and only one pair of k1 and k2?

One step further, how DES guarantee that by taking the same plaintext and different secret key, the encrypted outputs can never be the same?

I am learning the meet-in-the-middle on DES attack.

I don't know of any meet-in-the-middle attack on DES; I'll assume you're talking about 2DES (where you apply DES with one key $k_1$, and then apply another iteration of DES (possibly in decrypt mode) with another key $k_2$.

  why can we guarantee to find one and only one pair of k1 and k2?

We don't.  In fact, if we're just looking at a single plaintext/ciphertext block, there are likely to be circa $2^{48}$ $k_1, k_2$ pairs that map that plaintext block into that ciphertext block.

That is not a major obstacle; what we typically assume is that we have a second plaintext/ciphertext block that can be used for validation; given a candidate $k_1, k_2$ pair, we try those keys on our second plaintext block (and see if we get the second ciphertext block).  If it passes that, then it is most likely the correct $k_1, k_2$ pair.

This second check (which we may need to perform $2^{48}$ times) is less costly than the original MITM search, and so we mostly ignore that cost when estimating the cost of the attack.

  One step further, how DES guarantee that by taking the same plaintext and different secret key, the encrypted outputs can never be the same?

It doesn't; we generally assume that differing keys define different DES permutations (and so two different keys can map the same plaintext block into the same ciphertext block).


what benefits quantum offer over classical parallelism What is the benefits of quantum computing vs parallel processing using classical computer ?

Can classical parallel processors outperform  quantum computing ?

1. What is the benefits of quantum computing vs parallel processing using classical computer?

The answer is in terms of Cryptography;

Quantum Computing (QC)

Key search on Block ciphers;  Grover's algorithm is a brute-force quantum algorithm with complexity $\mathcal{O}(\sqrt{N})$ with asymptotically optimal on unstructured data.
Public key algorithms;

RSA factorization problem; Shor's algorithm can efficiently factor integer $n$ in $\mathcal{O}((\log n)^2(\log \log n)(\log \log \log n)$
Discrete logarithm problem; Shor's algorithm can efficiently solve.

Therefore, RSA, Diffie–Hellman, and Elliptic Curve Diffie–Hellman could be broken easily.

Parallelization

Parallel computing in keys searches only help linear time whereas using single QC already gives quadratic speed up. Examples are Distributed.net, DES Cracker, COPACOBANA hashcat
Parallel computing is used in factorization algorithms where the help again is linear with complexity;

General Number Field Sieve with superpolynomial scaling: $$\mathcal{O}(exp [ c (\ln n)^{1/3} (\ln \ln n)^{2/3}])$$

  2. Can classical parallel processors outperform quantum computing?

Firstly, quantum give new complexity classes;

  The class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time".7

  BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP.

Some $NP$ problems can be solved efficiently.

A Turing machine can simulate a QC and QC can simulate A Trung machine too,. So, once A QC is built, you can outperform a QC only by money.

Cost2

An important subject is also the cost of running the algoriths.

Daniel J. Bernstein asked the question in "Cost analysis of hash collisions: Will quantum computers make SHARCS1 obsolete". Some results if a QC is built;

Factorization; QC much more scalable and much more cost effective

The number-field sieve factors b-bit RSA moduli in time $2^{b^{1/3+\mathcal{o}(1)}}$
If a QC can be built for $b^{\mathcal{\Theta}(1)}$ Euros can factor b-bit integer in $b^{\mathcal{\Theta}(1)}$ seconds.

Pre-Image Search;

Traditional hardware can find in $2^bh$ operations
Quantum; much more cost effective

Grover $2^{b/2}h$ operations on $\mathcal{\Theta}(h)$ qubits.
Shor’s speedup from $2^{b^{1/3+\mathcal{o}(1)}}$ to $b^{\mathcal{\Theta}(1)}$

Collision search; He claims that all quantum algorithms upto his paper are less cost-effective than the traditional.
Parallelization
A size-$M$ machine finds collisions in time roughly $2^b/M^{3/2}$. if size $2^{b/3}$ than collision time is $2^{b/2}$ with $\epsilon$ time with $\epsilon$ probability.
a size-M QC after $2^{b/2}h\epsilon$ quantum operations each unit has $\epsilon^2$ success probability. After $2^{b/2}h/M^{1/2}$ total quantum operations the size-M machine has $M\epsilon^2$ success probability. If the size a quantum computer is $2^{b/3}$ then the time for finding collisions is approximately $2^{b/3}$. Compare to classical.

and he added;

  Anyone afraid of quantum hash-collision algorithms already has much more
   to fear from non-quantum hash-collision algorithms.

1 Special-Purpose Hardware for Attacking Cryptographic
Systems

2 Special Thanks to Ella-Rose for the article.


Why don't I see the IV in the FINISHED fragment in TLS_RSA_WITH_AES_256_CBC_SHA communication with OpenSSL? I'm implementing a TLS 1.2 server, comparing against OpenSSL to ensure I'm getting things right, and I've noticed that when the cipher is TLS_RSA_WITH_AES_256_CBC_SHA the IV isn't in the FINISH message.  OpenSSL is taking it from the keyblock data, derived via PRF from the master secret.

My understanding of the RFC (https://tools.ietf.org/html/rfc5246#appendix-A.1) is that GenericBlockCipher types have the IV as part of the fragment data.  So, AES_256_CBC is apparently a GenericStreamCipher, not a GenericBlockCipher.  But that's not what appendix C says.  Can anyone explain why OpenSSL isn't putting the IV in a FINISHED, v 1.2 message?

=====
(To confirm that I'm doing things right)

My SERVER_HELLO looks like this:

00000000: 16 03 03 00 31 02 00 00  2D 03 03 6E 97 FF 27 00  ....1...-..n..'.
00000010: 01 02 03 04 05 06 07 08  09 0A 0B 0C 0D 0E 0F 10  ................
00000020: 11 12 13 14 15 16 17 18  19 1A 1B 00 00 35 00 00  .............5..
00000030: 05 FF 01 00 01 00

type = 'HANDSHAKE'
tls_plaintext_maj = 3
tls_plaintext_min = 3
fragment =
    msg_type = 'SERVER_HELLO'
    body =
        server_version_major = 3
        server_version_minor = 3
        gmt_unix_time = 1855455015
        random_bytes = b'\x00\x01\x02\x03\x04\x05\x06\x07\x08\t\n\x0b\x0c\r\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b'
        session_id = b''
        cipher_suite = 'TLS_RSA_WITH_AES_256_CBC_SHA'
        compression_method = 0
        extensions = [Container({'extention_type': 'RENEGOTIATION_INFO', 'extension_data': b'\x00'})]

And OpenSSL seems fine with it, sending me CLIENT_KEY_EXCHANGE, CHANGE_CIPHER_SPEC and then this HANDSHAKE:

type = 'HANDSHAKE'
tls_ciphertext_maj = 3
tls_ciphertext_min = 3
fragment = b"\x87E\x08\xf4\xc9A\xadw\xe8i\xdb\xd6\xcb\x9d\x82\xa9\xdd\xa9\xee\x8d\xaa\x94\xfd\xc3\xc9\xf5\x94\xb4\x1d\xb4@\xd6\xc1\x8d\x16\xf0\x05\xbb!\xeb\x14HY\xe0\xb9\xa9i0+\xda\n\xe1\x87'V\x16\x1b\xce\xc41\xe6\x81\xe5\xb3"

That fragment can be decrypted with AES256, using:

client_iv = faaa0de35870f9041e40471b02d5dfd5
client_write_key = 702ca8bd8cc39a707b297f3ef164cb5c7a0f90f39a20fd86e3dfcdd2e01eeb62

Those keys are generated on my side via PRF and the shared master secret, and after decrypting it looks valid (there are 11 \0x0b bytes at the end, which is the expected padding).

In [8]: AES.new(bytes.fromhex('702ca8bd8cc39a707b297f3ef164cb5c7a0f90f39a20f
   ...: d86e3dfcdd2e01eeb62'), AES.MODE_CBC, bytes.fromhex('faaa0de35870f904
   ...: 1e40471b02d5dfd5')
   ...: )
Out[8]: <Crypto.Cipher.AES.AESCipher at 0x99fada7208>

In [9]: _.decrypt(b"\x87E\x08\xf4\xc9A\xadw\xe8i\xdb\xd6\xcb\x9d\x82\xa9\xdd
   ...: \xa9\xee\x8d\xaa\x94\xfd\xc3\xc9\xf5\x94\xb4\x1d\xb4@\xd6\xc1\x8d\x1
   ...: 6\xf0\x05\xbb!\xeb\x14HY\xe0\xb9\xa9i0+\xda\n\xe1\x87'V\x16\x1b\xce\
   ...: xc41\xe6\x81\xe5\xb3")
Out[9]: b'\x1c\xe3<\x88\xf4\xc0\x98\xe3\x8f\xbf\xc9\xa9"\'\x1bq\x14\x00\x00\x0c]\x95\xb8+l\x10 \xad\x99\xd8\xe2\x16=\xbf\x9e{\xc7\xd5\xbdLm\x04n\xa6/\xfb
\xfd\x8f\x96\x92\xe5\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b'

So, I'm pretty sure I'm doing it right.

Thanks...

Nothing is wrong, it is just that when decrypting CBC cipher text, the IV will only affect the decryption of the first block. The first cipher text block will be used as IV when decrypting the second cipher text block, the second cipher text block will be used as IV when decrypting the third cipher text block, etc.

Consequently, if the IV is prepended to the CBC cipher text, you may actually use any arbitrary IV you want when decrypting the cipher text, as long as you "decrypt" the IV as well and discard the first block of decrypted text prior to presenting the plain text to the next layer.

Hence, none of the information you provide in your question is inconsistent with the cipher text fragment really being a GenericBlockCipher.

Also note that in TLS 1.2, the IV of a GenericBlockCipher fragment will typically be generated randomly. In particular, it must not be identical to the IV optionally generated by the KDF in TLS 1.0 compatibility mode.


Why exactly Blowfish max key length is 448 Could anyone, please, tell me history of birth of Blowfish algorithm? Specifically, what is substantiation of Blowfish key length to be in range from 32 till 448 bits? Why, for example, it wasn't 64-512 so it's minimal key could be 2 times shorter than AES and maximal key could be exactly 4 times taller than AES with 256 bit key?

Bruce Schneier's Description of a new variable-length key, 64-bit block cipher (Blowfish) (in proceedings of the first FSE conference, held Dec. 1993) defines that Blowfish's key is of 4 to 56 bytes (32 to 448-bit), with this rationale for the maximum:

  The 448 limit on the key size ensures that the every bit of every subkey depends on every bit of the key. (Note that every bit of $P_{15}$, $P_{16}$, $P_{17}$, and $P_{18}$ does not affect every bit of the ciphertext, and that any S-box entry only has a $.06$ probability of affecting any single ciphertext block.)

Using more than 56 bytes of key for Blowfish is against its definition and design rationale: key bytes beyond the 72th have no effect whatsoever, and the few ones before may have somewhat less diffusion (though not nearly as badly as the above quote suggests). Some Blowfish implementations nevertheless accept keys with any positive number of bytes.


Is the following protocol perfect zero knowledge or computational zero knowledge? So I have this protocol for the hamiltonian cycle:

repeat t times:

Peggy chooses a random permutation $\pi$ on $V$, and computes $G_1=\pi(G)$
For each of the $\frac{|V|(|V|-1)}{2}$ possible edges of $G_1$ Peggy computes a different commitment and sends the commitnet to Victor. ($\forall v_1,v_2\in \pi(V)$ if $(v_1,v_2)\in \pi(E)$ then the commitment is on 1, and 0 otherwise)
Victor chooses a random $i\in {1,2}$ and sends it to Peggy
If $i=1$ the Peggy sends $\pi$ to Victor and reveals all the commitments on $G_1$. Otherwise, Peggy revelas the commitments on $|V|$ edges which form a hamiltonian cycle on $G$.
Victor checks Peggy's answer

So it's pretty easy to see that this is a zero knowledge protocol. How do I show if it's perfect zero knowledge or computational zero knowledge?

This is Blum's protocol for Hamiltonicity. The answer to your question depends on the commitments. There are two possibilities:

The commitments are perfectly hiding: in this case, the proof is perfect zero knowledge, but is only an argument (meaning that soundness is computational, and so only holds against a polynomial-time cheating prover).
The commitments are perfectly binding: in this case, the proof is only computational zero knowledge, but is a proof (meaning that soundness is unconditional).

Note that no commitment scheme can be both perfectly binding and hiding. In addition, the class of perfect zero knowledge proofs (unconditional soundness) is contained in $AM \cap co-AM$ and so is very unlikely to contain an $NP$-complete problem.


Does encoding a secret affect security? My question is simple. I have a secret that is generated with a 10 byte long pseudorandom generator library (e.g. Java's SecureRandom), that in theory provides a security equivalent to $2^{40}$ (birthday bound). This secret is encoded afterwards (e.g. Base64). This is supposed to reduce entropy, while extending the string lenght.

If I want to brute force the secret, does the encoding have any negative impact on the protection? (in other words, does it facilitate the brute forcing at all?)
My intuition is that the security is not affected, but I learnt to be extra cautious with this sort of things.

A byte is 8 bits; 10 random bytes are therefore 80 random bits, which is $2^{80}$ equiprobable alternatives (not $2^{40}$), which is 80 bits of entropy.  (Unless your 10 byte random string is actually an ASCII representation of a 40-bit hexadecimal value; since SecureRandom outputs full range byte[] I'll assume it's not that.)

  This secret is encoded afterwards (e.g. Base64). This is supposed to reduce entropy, while extending the string length.

This "entropy reduction" isn't real.  Any Base64 encoder is a one-to-one function—each of the $2^{80}$ inputs in your example is mapped to a unique output.  There are therefore $2^{80}$ unique possible outcomes as well, each one equally likely, and thus 80 bits of entropy like originally.

What's probably confusing you is that the binary representation of the Base64-encoded string is longer than 80 bits, but it's not made of uniform random bits, so in that sense it's not a full-entropy string—the 14-ish bytes in the Base64 string are 112 bits long but would only collectively have 80 bits of entropy.

  If I want to brute force the secret, does the encoding has any negative impact on the protection?

Not really.  Again, $2^{80}$ possible outcomes, all of them equally likely.


How long would it take to brute force an AES-128 key? How long would it take to crack a AES-128 key using the most advanced technology currently available? The hardware can be anything, be it a high-performance CPU, GPU or even FPGA?

I wrote a similar answer in the past, where the assumption was half the key is known. Since then, the bitcoin hashrate almost tripled (it's used in the estimation, as below). The estimation for half the known key would therefore be $~3.6$ seconds.

But to brute force a $128$ bit key, we get this estimate:

Let's assume we can test as many keys as the current hashrate of the bitcoin network. There special purpose hardware is used and it's for SHA-256, this makes it not directly usable, but it should be close. That means we could test approximately $5 \cdot 10^{18} \approx 2^{62.117}$ encryptions per second. Regarding the type of hardware: For some years now bitcoins are mined mostly with ASICs, which are faster and more efficient than all of those options you listed. That's special purpose hardware, which can't be programmed to do anything else - but it's the best we can do for speed.

That means, for the full key we need $\approx 2^{128} / 2^{62.117} = 2^{65.883}$ seconds. This is approximately:

$68 \cdot 10^{18}$ seconds
$18.9 \cdot 10^{15}$ hours
$2.158 \cdot 10^{12}$ years. Written as integer: $2,158,000,000,000$

Since that number is still slightly hard to grasp, this is the age of the universe: $13.799 \cdot 10^9 = 13,799,000,000$

So a rough estimation would be $156.4$ times the age of the universe for testing all keys. You can divide that number by $2$ to get the average time to find the correct key.

Related question: How much would it cost in U.S. dollars to brute force a 256 bit key in a year?


One-wayness proof of Elgamal Here in the proof of Elgemal one-wayness:

Consider an adversary V that can invert random Elgamal encryptions with $ε$ probability.
$V *$ : Adversary to compute the Diffie-Hellman function:
On input ($A = g^{a},B = g^{b}$), we must output $g^{ab}$.
Give $A$ to $V$ as the public key.
Pick a random $Z \in G$ and give $(B,Z)$ to $V$ as the ciphertext.
When $V$ outputs $m$, we output $Z / m$.
Note that the distribution $(A,(B,Z))$ does indeed correspond to a random Elgamal public key and encryption of a random message under that key. Thus, with probability $ε$, $V$ outputs the "correct" plaintext $m$ (that is, $m$ such that $Z = mg^{ab}$). When this is the case, the output of $V^*$ matches the Diffie-Hellman function. By our assumption that the CDH assumption holds for the underlying group, $ε$ must be negligible, as desired.

For the first CPA security proof described here, I think it makes adversary guess the value of $a$ or value of $b$. If it can guess one of those values, then it can know which message is encrypted ($m0$ or $m1$). Even it can guess one of those values, and decrypted plaintext is neither $m0$ nor $m1$, then it can know that $c$ is randomly generated. Is it right? But in the second proof for one-wayness of encryption described above, as $Z$ value is selected randomly from $G.$ I can't catch the purpose of checking  $Z = mg^{ab}$. Can anybody help me?

You are confusing two different security notions.

The proof you describe is regarding the Onewayness under chosen-plaintext attacks (OW-CPA). Basically, this notion covers the idea that it shouldn't be possible for an adversary to decrypt a given ciphertext (i.e., encryption is one-way), even if he can encrypt chosen plaintexts. As the proof shows, ElGamal is OW-CPA secure under the Computational Diffie-Hellman (CDH) assumption.

However, you are asking about indistinguishibility (i.e., guessing if an encryption is for one message or another). That's a different notion (and actually, a much more relevant one). It can be shown that ElGamal is IND-CPA secure under the Decisional Diffie-Hellman (DDH) assumption, which is weaker than CDH. Your understanding is correct: if an adversary can break OW-CPA, then it certainly can break IND-CPA. In security we are actually interested in the contrapositive: if a scheme is IND-CPA, then automatically is OW-CPA.

Regarding the OW-CPA proof of ElGamal, you have to know that in the OW security game, the adversary does not choose the underlying message, but the challenger. That means that the challenger doesn't even have to know the actual underlying message for the challenge ciphertext (that's why it can output a random $Z$ for the ciphertext).

Now, if an adversary can break OW-CPA, it means that he is capable to decompose $Z$ into $m$ and $g^{ab}$, in order to output $m$. The challenger then uses the result from the adversary to compute $g^{ab}$ as $Z/m$. Note that each time the adversary outputs a correct $m$ (which happens with probability $\epsilon$), the challenger succeeds in computing $g^{ab}$, since for each random $Z$, there is always one $m$ such that $Z = m g^{ab}$.


Is it possible to distinguish a securely-encrypted ciphertext from random noise? Say I have a bunch of data encrypted with a secure block cipher (such as AES). An attacker has unlimited access to this encrypted data. The attacker doesn't know whether the data is encrypted or if it's just purely random bits. Is it possible (even theoretically) for the attacker to distinguish the encrypted data from purely random bits?

There seems to be many questions asking whether or not it's possible to identify a particular encryption scheme from the ciphertext, but what I want to know is if it's even possible to determine that the data is encrypted in the first place (as opposed to being random bits).

It... depends.

AES is a block cipher. It works over 128-bit blocks. For a given key, AES is a permutation of the $2^{128}$ possible values that 128-bit blocks may assume. As a purportedly secure block cipher, AES is supposed to be indistinguishable from a random permutation, i.e. a permutation selected randomly and uniformly among the $2^{128}!$ possible permutations of the space of 128-bit blocks.

If you consider AES used in counter mode (CTR): some piece of hardware encrypts the successive values of a counter with AES, and spews out the concatenation of the encrypted blocks. You challenge the attacker to distinguish between such a stream, and a purely random stream of equal length. Since AES is a permutation, the AES-CTR stream will never include twice the same block value (by encrypting two distinct counter values, you necessarily obtain two distinct block values). However, the purely random stream is also expected not to repeat the same 128-bit value, until you reach a length of about $2^{64}$ blocks, i.e. quite a lot.

In that sense, AES-CTR is supposed to be indistinguishable from random noise: if AES-CTR was distinguishable, then this would imply that AES (the block cipher) is not indistinguishable from a random permutation, and that would be viewed as a structural weakness in AES. With a $k$-bit key, the cost of distinguishing AES from a random permutation should be $2^{k-1}$, no less (that's the average cost of brute-forcing the key). No such structural weakness is known yet for AES (for AES-192 and AES-256 there are some related-key attacks, but they imply using several AES instances with specific keys which are linked to each other algebraically).

Now, although indistinguishability is academically important (a cipher is deemed weak if it cannot achieve it), it is rarely relevant to practical situations. Most protocols which use encryption very straightforwardly admit to using a specific encryption protocol. For instance, if you use SSL/TLS, the client and server announce in the initial handshake message what kind of encryption algorithm is used, and this is not a problem for practical security. If security crumbles when the algorithm is known, then this is also considered as a structural weakness of the algorithm.


Multiplicative Inverse in AES I want to calculate the S-box for AES. But I have a problem with the multiplicative inverse step. For example, the inverse of 95 is 8A.

I don't know how to get this result. How is the multiplicative inverse computed?

The inverse in AES is defined over a particular field. All the operation are done in this field.
The Rijndael finite field is defined as follow: $GF(2^8) = GF(2)[x]/(x^8 + x^4 + x^3 + x + 1)$.

The "numbers" are a representation of polynomials (a byte represents coefficients of a polynomial):

0x95 = 1001 0101 = $x^7+x^4 + x^2 + 1$

0x8A = 1000 1010 = $x^7+ x^3 + x$

And the product of the two polynomial reduced modulo the irreductible polynomial is 1, as expected.

There are several way to implement the inversion and the affine transformation described in the AES to get the final SBox. Once you get the math, you may choose one way or the other, keep in mind that you can avoid to implement all the algebraic structure and a function taking as input only a byte (cfr: https://en.wikipedia.org/wiki/Rijndael_S-box#Alternate_equation_for_the_affine_transformation)

You may find more information here: https://en.wikipedia.org/wiki/Rijndael_S-box and https://en.wikipedia.org/wiki/Finite_field_arithmetic#Rijndael.27s_finite_field and Galois fields in cryptography


How to take SHA-1 safely for my particular case? Let me ask about my toy passwords generator program X5 which I want to improve.
X5 uses a secret key and a public key to generate a password.Where any public key is supposed to be known to hackers in the worst case.

pwd = sK + pk

To describe details, let me define some expressions.

each of K and k denotes a seed key but k corresponds to just one password generation,
   whereas you use K for all password generations;
K(n) means a seed key of n length;
pwd(n) means a password of n length;
sha1( s, n ) returns the first n characters of sha1(s),
where sha1 means recursively applying sha1 algorithm
on the input string for a constant many many times.

Using the new expressions, my algorithm can be written as follows.

pwd(n) = sha1(
               sha1( sK(5) + pK(3 or longer) , 5 )
         , n);

I want to X5 prepares for the following context of a user .

The algorithm of X5 is in public.
HackerA knows just one generated password pwd_X ;
HackerA knows all public keys, of past and of future .
HackerA even knows that pK_X was used to generate pwd_X.
HackerA tests all possible patterns to know sK.
HackerA knows all pairs of account names and servers.
HackerA tests all passwords possibly generated by X5 against all servers.

Let me ask , if the following algorithm differs much than the previous one.

pwd(n) = sha1(
               sha1( sK(5) + sha1( pK(3 or longer) ,3 ) , 5 )
          , n);

And which one is more secure?

Thank you in advance.

The main difference between your two algorithms is that the second one takes longer because of your additional hashing of the "public key". Also, by the truncation of this hash to 3 characters (are this bytes, hex digits, base64 digits?) could lead to collisions of different public keys to the same hash, which is much more unlikely to occur if you use the full hash.

The same kind of collision is possible after your "main" hash, don't do any truncation before the final one, please.

The general problem with such password hashing schemes is that, given the output and the "public key" (this is usually called "salt"), it is possible to brute-force the "secret key", if there are not many possible values for it. A five-character password is not enough by any measure.

But even with a "good" password, good practice is to not use a fast hash function like SHA-1 (or some small number of iterations of it), but a slow one. (Using some repetitions is a good start, but you normally want to input the secret again in each iteration, to avoid collisions of different secrets.)

Have a look at What makes a hash function good for password hashing? for details and some example functions.


Prove that (m1 ⊕ m2) = ek(m1) ⊕ ek(m2) for a 8-bit blocks i/p encryption system I tried to work this out but I'm stuck at finding a relation between $c$ and $e(k)$:

An encryption system accepts 8 bit-blocks as input.
The encryption is done by XOR'ing the bits with an 8-bit key.
Prove that:

$(m_1 ⊕ m_2) = e_k(m_1) ⊕ e_k(m_2)$

There does not exist a message $m$, such that $e_k(m) = m$, except when $k$ is all 0's.

Let $k$ be the 8-bit key.  Since encryption is simply done by XORin the plaintext with the key, i.e. $e_k(m) = k \oplus m$, we have:

$$e_k(m_1) \oplus e_k(m_2) = (k \oplus m_1) \oplus (k \oplus m_2).$$

Now, the thing you need to know about XOR is that it obeys the same commutative, and associative laws as normal addition, that is:

$$a \oplus b = b \oplus a$$
$$a \oplus (b \oplus c) = (a \oplus b) \oplus c$$

and it also obeys the cancellative laws:

$$a \oplus a = \bar 0$$
$$a \oplus \bar 0 = a$$

where $\bar 0$ denotes the string of all zero bits.

Using these algebraic laws, you should be able to show that the two $k$'s on the right hand side of the equation above will cancel out, leaving only $m_1 \oplus m_2$.

Similarly, you should be able to show that, if $k \oplus m = m$, then $k = \bar 0$.  The easiest way is probably to observe that, if $a = b$, than $a \oplus c = b \oplus c$.  Thus, you can XOR both sides of the equation $k \oplus m = m$ with $m$, and then apply the cancellative law.


Can the same One-Time-Pad be re-used with some tricks Let’s say I have a message $m$ of $n$ bits. And a predetermined pad of $k*n$ bits. And for every bit $b$ of this message $m$, I’m creating random sequence $s$ of $k$ bits.

I also have a predetermined boolean random function $f$ (imagine something like this: $f(s) = hash(s)\ mod\ 2$).

For each bit $b_i$, I choose a random value for $s_i$, so that $f(s_i)=b_i$.

So, I can construct a padded version of $m$ like this: $m_p= s_0 || s_1 || ... || s_n$, removing the padding is trivial.

The encryption is also straightforward XOR of the $m_p$ value with the predetermined pad of the same length ($k * n$)

Can this protocol justify/enable reusing of the same pad over and over again providing OTP-Like security?

Equivalent text-based formulation of the scheme:
One comes up with a fresh, random hash pre-image for each message bit that when hashed yields the message bit as the LSB. You then transmit the pre-images and encrypt them with the re-used OTP.

Based on comments it seems the question asks if this is as secure as OTP as opposed to finding a practical attack.

It is clearly not as secure as OTP. It is not information thetorical secure. With sufficient messages totalling more than key size we can brute force the key, just iterate over possible keys until you find one which works with all messages.

With a OTP when the total message size never exceeds the key size, no compute power will allow you to brute force the key, all messages are equally likely and knowing part of the message doesn't help as the key is never reused.

Edit: Even an attack with $O(2^{kn})$ is sufficient to make it not information theoretical secure. but we can do at least somewhat better.

With $O(k)$ message pairs we can break the key with O(n*2^k) work. work one segment at a time. Iterate over all $2^k$ possible key segments, and check the messages, each message will exclude a bad key with probability 0.5 so we only need a few message pairs to rule out all false keys.

I reserve judgment regarding security of this with large k, and secure hash.


EC scalar multiplication with zero scalar Is the elliptic curve scalar multiplication $[n]G$ defined if $n=0$?
I saw multiple software implementations with multiple results such that, $[0]G=0$ or $[0]G=G$.
This made me wonder, how can i compute $[0]G$ on 25519 curve, where G is the base point. $G=(9,14781619447589544791020593568409986887264606134616475288964881837755586237401).$
Also, is [n]$\mathcal{O}$ defined?

I saw multiple software implementations with multiple results such that, $[0]G=0$ or $[0]G=G$.

As stated in the comments, we define $[0]G = 0$, anything else is incorrect
I thought I'd outline why we define things we did.
What we want is to have $[a+b]G = [a]G + [b]G$ be true for all integers $a, b$, and all points $G$.
If it is true for all integers $b$, it must be true for $b=0$, hence we must have:
$$[a+0]G = [a]G + [0]G$$
This obviously simplifies to $[a]G = [a]G + [0]G$, and this is true only if $[0]G$ is the group identity, that is, only if $[0]G = 0$


Solve a problem, thought it was hash length extension, hours later, am I wrong? Here is my situation. I'm working with an application for which uses hashing to authenticate data.

I have a string, which is hashed. It is, like in a hash length extension attack, H(key:known_value)

This hash is incremented by a nonce upon repeated attempts. On the first attempt there is no nonce, further attempts are H(key:known_value:nonce)

I believe I misunderstood a hash length extension attack (and was up for 9 hours last night learning that) in that by knowing the hash value, and the length of that entire hashed string, that I could add a nonce and get the same hash?

Not sure if I'm making sense, so let me demonstrate with example values:

hash("IamSecret:YouKnowMe") = 389fiu3vb93h39v (yes, not a real hash)
hash("IamSecret:YouKnowMe:1") = f5d725d78223hjd2d2 (also made up)

I thought that a hash length extension would allow me to take the first hash, "389fiu3vb93h39v" and knowledge of the length of the secret (9) and the known data (":YouKnowMe") and append my data (":1") and come up with "f5d725d78223hjd2d2"?

But after 9 hours of messing with it, it seems thats NOT possible? What a hash length extension attack would allow me to do is to take my known values above, and come up with a string (something like :YouKnowMe\x80\x00\x00.......\x00:1) and figure out what the hash would be **IF I DID **hash("IamSecret:YouKnowMe\x80\x00\x00.......\x00:1")?

Is my understanding correct?

And if so, is there ANY way to do what my original issue was? I know the hash algorithm used, I know the hashed value of secret:known, I know 'known', I know the length of secret. Can I ADD DATA to 'known' and get the same hash that the client app would get if it just hashed secret:known:added_data?

I'm running on 4 hours sleep, sorry if my question is confusing :)

Length extension attacks exploit the pattern that it's possible to use H(k || m1) to compute H(k || m1 || m2) without knowing the value of k, but it is restricted to messages m2 of a particular form.  Which is, they have to begin with the padding p that the hash algorithm applies to expand to a multiple of the block size.  This is critical, because it's what allows the attack to infer the internal state of the hash when it starts to process the non-padding part of m2.  Without the padding, the hash algorithm never gets to the state represented by the original output.

In your example, "IamSecret:YouKnowMe" and "IamSecret:YouKnowMe:1" don't follow that pattern - the second message does not have the padding before the new data.  Therefore you can't know the internal state when it starts consuming the nonce, and so you can't predict the output.

The authentication protocol in your application is not strong, you probably want to use HMAC or similar.  It's not clear to me if it's vulnerable to a length-extension attack; I don't quite understand which of the inputs are under control of the attacker (presumably known_value) and what the hash is used for.

See also Understanding the length extension attack for an accessible write-up.


Fibonacci LFSR, recovering previous bits Suppose somewhere is Fibonacci LFSR, we know that it has 7 cells and feedback taps are cell 2 and 7.

We intercepted part of a stream, and part intercepted is 1010101.

Is it possible to recover (preceeding)previous bits from this stream using this information?

Yes. just run the lfsr backwards, so if you have $$s(t)=s(t-2)+s(t-7)$$ use $$s(t-7)=s(t-2)+s(t)$$ all mod 2 with $$(s(-6),\ldots,s(0))=(1,0,1,0,1,0,1)$$ your initial loading.


Fuzzy Extractor for Binary Sequence I was implementing Fuzzy Extractor on two close (noisy data). It's straight forward to use it to reconcile two close sets as per implementation given in https://www.cs.bu.edu/~reyzin/code/fuzzy.html, given contents of set are decimal number because:
 1. It compares sets, hence position of numbers in set does not matter.
 If I have two binary sequence extracted from close secrets can I use this extractor to correct two close binary sequence, say 10% of bits are mismatching?

As per documentation of Pinsketch we cannot use $0s$. Since set matters,
$[10011]$ and $[01011]$ will match as contents are same except order of $0$ and $1$.

Papers like [LLYM17] report of using Binary bit stream but I cannot find how this implementation based on works of Dodis et.al can be used here.

[LLYM17]: Xinghua Li, Jiajia Liu, Qingsong Yao, Jianfeng Ma, Efficient and Consistent Key Extraction Based on Received Signal Strength for Vehicular Ad Hoc Networks, in IEEE Access 2017.

You can use pin sketch. Consider the set of number [0,1,2,3,4,5,6,7]. The presence of a number can represent the presence of a 1 at that bit position in an 8 bit number.

E.G.

[0,2,4,6] == 10101010 == 0x55

[0,1,2,3] == 11110000 == 0xF0

Extend to a useful size (like 2040 bits which maps nicely to a BCH code) and you are comparing sets that have on average 1020 unique values, each showing the positions of the ones.


Benefit of capitalization when using Diceware passphrases? If I use a Diceware generated passphrase of any given length, will capitalizing the first word (or any word for that matter) effectively double the number of combinations that would have to be tried in a brute force attack.  In other words by capitalizing one word of the passphrase chosen from a list of ~7500 words haven't I now created a single list of ~15K words: abc, def … xyz, Abc, Def … Xyz.

Even if I told an attacker which word list I used and that I capitalized the very first word of the passphrase, wouldn't the random nature of the dice throw create a larger space to search through before a successful guess?

Yes, randomly choosing whether or not to capitalize the first word in the passphrase doubles the number of possible passphrases, and thus also doubles the average time needed for a brute force attacker to guess the correct passphrase.

Note that doubling the average time needed to crack the passphrase is equivalent to increasing the entropy of the passphrase by one bit.  In comparison, adding one more word to your Diceware passphrase will increase its entropy by 5 log2(6) ≈ 12.9 bits, multiplying the average time needed to crack it by 65 = 7776.

Of course, there are several other capitalization choices one could more or less reasonably make, such as:

all lower case,
ALL UPPER CASE,
Title Case (First Letter Of Every Word Capitalized),
LeEt CaSe (EvErY sEcOnD lEtTeR cApItAlIzEd),
reversE titlE caseE,
tITLE cASE wITH cAPS lOCK oN,
Only first letter capitalized,
oNLY FIRST LETTER IN LOWER CASE, etc.

Choosing randomly from among, say, the eight capitalization options above would make the passphrase eight times harder to guess, increasing its entropy by log2(8) = 3 bits.  You could also randomly decide e.g. whether or not to use spaces between the words in your passphrase, again doubling the average time to guess it and increasing the entropy by one bit.  And including the possibility of using, say, hyphens or periods or underscores instead of the spaces would add a bit or two more entropy yet.

That's still a lot less than just making the passphrase one word longer, though.  To achieve a comparable increase in entropy, you've have to literally choose the capitalization and punctuation of your passphrase randomly from among almost eight thousand options.  Good luck remembering that!


How are Elliptic Curve private and public keys actually used to encrypt or sign data? I've read article after article about curve parameters, generator points, the dot operation, and how you dot the generator point priv times to get the pub point and voila you have ECC! That's where the articles all stop. But how are the number priv and the point pub used to modify data during encryption or signing?

The simplest application of elliptic curves is Diffie–Hellman key agreement.  In a curve $E/k$ over a field $k$ with a standard base point $P \in E(k)$ of large prime order $\ell$ among the $k$-rational points (loosely, the points whose $x$ and $y$ coordinates are in $k$, and not in a field extension of $k$), Alice picks a uniform random scalar $a \in \mathbb Z/\ell\mathbb Z$ and publishes the point $A = [a]P$, the scalar multiplication of the standard base point $P$ by $a$; Bob does likewise with $b$ and $B = [b]P$.  Now Alice can compute $$[a]B = [a]([b]P) = [a\cdot b]P,$$ and Bob can compute $$[b]A = [b]([a]P) = [b\cdot a]P = [a\cdot b]P.$$  They can then both hash this common curve point into a shared secret $k = H([a\cdot b]P)$, and use $k$ for symmetric-key authenticated encryption, such as AES-GCM.

This is a high-level overview—there are, of course, devils in the details like how to choose the curve, how to represent the curve points, how to perform the computation, etc., some of which are addressed in SafeCurves.

But what about public-key encryption and public-key signature?

Encryption

Instead of using a long-term key pair $(a, A)$, when Alice wants to send a message to Bob she can generate a temporary secret scalar $t$, compute a temporary public key $T = [t]P$, compute a temporary session key $k = H([t]B) = H([t\cdot b]P)$, and transmit $T$ as associated data with a symmetric-key AEAD box (authenticated encryption with associated data) under $k$.

Then Bob, on receipt of $T$ and an AEAD box, computes $k = H([b]T) = H([t\cdot b]P)$, and uses that to open the AEAD box.

That's it.  It's just a DH key agreement with a temporary key pair.

Signature

There are a few different signature schemes out there based on elliptic curves.  For a detailed discussion of some of the design choices that go into conventional elliptic-curve signature schemes, see djb's blog post on how to design an elliptic-curve signature system.  Here's a couple of (very different) examples:

Example 1: EdDSA: Edwards-curve Digital Signature Algorithm (simplified)

This is the general form of the widely used Ed25519 signature scheme, which widely deployed and understood and considered by many to be the modern standard signature scheme.

Parameters.
A field $k$, a twisted Edwards curve $E/k: y^2 - x^2 = 1 - d x^2 y^2$ over the field $k$, a standard base point $B \in E(k)$ of large prime order $\ell$, and a hash function $H\colon \{0,1\}^* \to \{0,1\}^{512}$.

Public keys.
A public key is the representation of a point $A \in E(k)$.

Signatures.
A signature on a message $m$ is the representation of a point $R \in E(k)$ and a scalar $s \in \mathbb Z/\ell\mathbb Z$ satisfying the verification equation $$[s] B = R + [H(\underline R \mathbin\Vert \underline A \mathbin\Vert m)] A.$$  Here $[s]B$ means scalar multiplication of the point $B$ by the scalar $s$, and $\underline R$ means the bit string encoding of the point $R$.

Private keys.
A private key is a secret 256-bit string $k$ chosen uniformly at random.  The 512-bit hash $H(k)$ is split into two 256-bit halves, the first interpreted as a scalar $a \in \mathbb Z/\ell\mathbb Z$ and the second taken as a bit string $h$.

To sign a message $m$, the signer computes the scalar $r = H(h \mathbin\Vert m)$, the point $R = [r]B$, and the scalar $$s = r + H(\underline R \mathbin\Vert \underline A \mathbin\Vert m) a.$$

Verifying that signatures created this way satisfy the verification equation is left as an exercise for the reader.

Example 2: BLS signatures using pairing-based cryptography

The Boneh–Lynn–Shacham signature scheme uses a function called a pairing, which is a bilinear map $e\colon E(k) \times E(k) \to G$ from the group $E(k)$ of $k$-rational -points on a curve $E/k$ with coordinates in the field $k$ to a multiplicative group $G$, typically the multiplicative group $(\mathbb Z/p\mathbb Z)^\times$ of integers modulo a prime $p$.

‘Bilinear’ means that if $X$, $Y$, and $Z$ are elements of $E(k)$, then $e(X + Y, Z) = e(X, Z) \cdot e(Y, Z)$ and $e(X, Y + Z) = e(X, Y) \cdot e(X, Z)$, i.e. that addition of two inputs carries through to multiplication of the outputs.  This further means scalar multiplication $[a]X$ the curve carries through to exponentiation $g^a$ in the target group: $e([a]X, [b]Y) = e(X, Y)^{a b}$.

Pairing-based cryptography is not as widely deployed, and its security is not as well-understood, but it admits very short signatures (half the size of Ed25519 with a curve of comparable conjectured security, for example), and it is simple to state.

Parameters.
A field $k$, an elliptic curve $E/k$, group $G$, a bilinear map $e \colon E(k) \times E(k) \to G$, a standard base point $B \in E(k)$ of large prime order $\ell$, and a hash function $H\colon \{0,1\}^* \to E(k)$ mapping messages to curve points.

Public keys.
A public key is the representation of a point $P \in E(k)$.

Signatures.
A signature on a message $m$ is the representation of a point $S \in E(k)$ such that $$e(S, B) = e(H(m), P).$$

Private keys.
A private key is a secret scalar $p \in \mathbb Z/\ell\mathbb Z$ such that $P = [p]B$, the scalar multiplication of $B$ by $p$.

To sign a message $m$, the signer simply computes $S = [p] H(m)$.

Verifying that signatures created this way satisfy the verification equation is left as an exercise for the reader.


Multiple Rainbow Tables and their Success Probability I am trying to understand the calculations for the success probability of finding an unknown key using rainbow tables.

Basically, I have a target success probability, a known keyspace of size $N$ and want to derive the neccessary table building parameters: the number of chains $m$, and the length of each chain $t$, and potentially the number of tables $l$ (see below).

The original paper by Oechslin gives the success probability of a single $m \times t$ table for finding a key in a keyspace of $N$ keys as
$$
P_{table} = 1 - \prod_{i=1}^{t}\left(1 - \frac{m_i}{N}\right)
$$

with $m_i$ recursively defined as $m_1 = m$ and $m_{n+1} = N\left(1-e^{\frac{-m_n}{N}}\right)$.

The appendix in the paper gives an explanation of this formula, which I can mostly follow. However, with $m_i$ defined like above, I cannot see how one could derive the parameters $m, t$ except by just evaluating the function, which is quite computationally expensive.
These posts suggest, that one just fixes $m$ to the available amount of memory and then scales $t$ to achieve the targeted success probability. This post links to a paper discussing this problem, but as far as I can tell perfect tables are assumed and the computations do not get much simpler.

It is argued, that the rainbow tables have a similar success probability to multiple Hellmann tables (each using a different reduction function), totaling to the same size as a single rainbow table. However, I could not find a proof for this claim anywhere.

Additionally, in Section 4.3 of Oechslin's paper, multiple rainbow tables are used to achieve a higher success probability than with a single table.

In what way do these multiple rainbow tables differ from each other?
How does using multiple tables differ from just constructing a single larger table?
How does using multiple rainbow tables increase the success probability?

With perfect rainbow tables the math for evaluating is much simpler but the math for how long it takes to the build them becomes complex.

It all has to do with collisions and since we eliminate almost all of them the math is simple.
Let's look at how collisions behave in a classic distinguishing point table.
When adding a new row each value may collide with any previous $m*t$ point and the continuation to the end of the row will obviously collide as well. So any collision costs us the whole row not just the colliding point. When we split into multiple tables this changes.  A collision with within the table is as before but is less likely as we separated our points between tables so each table is much smaller. A collision across table isn't that bad because because only the single point will collide the next point in each chain will be different in each table so this isn't very bad and is in many cases ignored in analysis.

Rainbow tables are similar, each column has a different hash function so a rainbow table column is similar to a separate table. Only $\frac{1}{t}$ collisions are in the same column and will continue to collide till the end of the row. Cross column collisions like cross table collisions don't propagate and aren't expensive.
$t$ distinguishing points tables with $m$ rows and $\sim t$ columns each have similar coverage to a single rainbow table with $m*t$ rows and $t$ columns. The obviously both take $m*t$ space. But the lookup time in the rainbow version is half, because columns near the end are cheaper to check.

As to the math, the first formula is easy, $m_i$ are the number of distinct values in each column and the probability of appearing in each column is independent so the coverage is $1$ minus the probability of missing all columns. The next formula is the tricky one. Each column has fewer distinct values then the previous one. This comes from balls into bins theorum. Throwing $m$ balls into $n$ bins. The expected number of empty bins is $n*(1-\frac{1}{n})^m$ and subtract that from $n$ you get the number of different values. The version with $e$ is an excellent aproximation for large $m,n$.

As to multiple rainbow tables:
The first column of a rainbow table is special we can easily ensure it is unique. Adding columns each column is less effective. If we break into multiple tables we need to look up in each of them independently so splitting into two tables cost us lookup time. but collisions between tables are a non issue. Try punching in some numbers to get a feel for it.
If our search space n is 2^50 and we have a memory budget for 2^30 rows. Let's consider one or two rainbow tables. If we want a probability of 50% in a single table we need 869,000 columns. For two tables each with half the rows we will need each table to have a success rate of $1-sqrt(1-0.5)$ which ~0.292 This will require 790,000 columns. Which is better? The single table, because it's runtime is $869000^2/2$ which is less then $2(790000^2/2)$
But what if we want a high probability for example 95% ? for a single table we will need to go all the way up to 7,300,000 columns. But two tables with half the rows will need only 4,680,000 rows to reach 77% each.  Now we punch in and see the two tables are more then twice as fast then the single table.
If you fix sigma(m) for all tables and p, you can iterate over small table counts for each find the necessary t and pick the optimum.


In cryptography, what is "fractionation"? I understand how fractionation is used in the straddling keyboard, which is an important feature of the VIC Cipher, and in the Polybius Square of the ADFGVX cipher, but I am not sure how to describe its cryptographic function and benefit.

It helps spread the redundancies of the plaintext over the ciphertext, and that is diffusion. In doing so, it increases a message's uncertainty.

But on the face of it, fractionation also looks like a kind of substitution.

What exactly is fractionation, and what can it achieve in terms of information theory?

...looks like a kind of substitution.

It's perhaps more similar to encoding, say to ASCII, Baudot code or "dits & dahs" (morse code). And as the name implies, fractionation breaks up the message characters into smaller pieces (fractions) that then exactly represent those characters.

It was used in the more classical ciphers like transpositional ones.  Probably before the common use of computing machines.  The transpositions occurred on a character by character basis. The coordinates on a Polybius square can serve a similar function to that of an index into an S-box/lookup table. Or they can be otherwise manipulated in ways that a single character can't be.  Since the advent of modern computers, this fractionation occurs automatically when the characters are represented as bits within a block of bytes.  The term does not seem to appear in contemporary cryptography.

I suggest that the benefit is not for elimination of message redundancy, but for assisting with diffusion.  Substitution and permutation are entirely mathematically possible with a human alphabet.  You'd just have multi-character substitution boxes, so a three character substitution box would accept input like ggn and output yqy.  You'd permute single letters between them as we do today. It would be cumbersome though as such an s-box would be at least 19,683 entries long ($(26 + 1)^ 3$).  Numbers extra.  And their efficient generation via polynomials would be problematic. Algebraic qualities, avalanche and linearity were not well appreciated then.

So now we fractionate/encode to numbers and bits, and manipulate, substitute and permute them instead.


How to calculate Trace function for a point on an elliptic curve I encountered trouble with calculating Tr (trace function) for points on an elliptic curve in polynomial basis ( $GF(2^m), m = 431$). Maybe there are any assumptions that can simplify and allow efficiently to calculate Tr operation?
I used the Seroussi approach to decompress points but it seems like I need some basic knowledge.

Let $E$ be an elliptic curve defined over $F_q$, and let $\#E(F_q ) = q +1−t$. In this case, $t$ is called the trace of $E$.

Also, $\#E(F_{q^n} ) = q^n + 1 − V_n$ for all $n ≥ 2$, where $\{V_n\}$ is the sequence defined recursively by $$V_0 = 2, V_1 = t,\text{ and }V_n = V_1V_{n−1}−qV_{n−2}$$ for $n ≥ 2$. In your question it's enough to compute $V_{431}$.

For more details, see Guide to Elliptic Curve Cryptography.


Public key cryptography for website access I recently stumbled apon a though, is there a way to make a website only available to the people that have a public key, just like SSH key authentication, the private key is stored the server, while the public key is stored on the client. When the client tries to connect, the server looks for the public key to see if it is applicable, if it is then the client will be able to see the page, if it isn't, the client would be declined.

Has this already been put to practice, if so, what is it called?

Yes and no.

Yes, there is a public-key SSH-like authentication on the internet which is supported by all major browsers and TLS implementations: TLS client authentication. You just have to specify a list of CAs (possibly your own, non-publicly-trusted CA) that are allowed to issue valid certificates and they and only they are going to yield a successful connection.

However there are drawbacks / little benefits to it which is why it isn't actually deployed usually.

No, it is the client who has to own the private key for authentication. Suppose it was otherwise. Everybody could potentially learn the public key, otherwise it would be just a password. So if everybody can learn it, everybody can use it to impersonate the legitimate client making the entire authentication process completely pointless.


why are non singular curves used in elliptic curve cryptography? It is not possible to draw  tangent at all the points of a singular curve. What is the specialty of this and how it is related to cryptography and elliptic discriminant?

Not-so-useful answer: An elliptic curve is by definition a non-singular curve. Therefore by definition we use non-singular curves in elliptic-curve cryptography.

Why not use singular curves? It turns out that the group structure on those curves is isomorphic to the multiplicative group of a (quadratic extension of) a field. Therefore the discrete logarithm problem is not harder than of that in a finite field, so there is little reason to use the curve in the first place.

The discriminant characterizes all curves which are non-singular. In other words, the curves that are non-singular are exactly those for which the discriminant $\Delta$ is non-zero.


Diffie-Hellman using a different modulus on both sides For Diffie-Hellman Key Exchange, the used modulus is the same throughout the process. Is it possible to use 2 different for both sides? For example,

$A \gets M^{d_1} \pmod{n_1} $
$B\gets M^{d_2} \pmod{n_2} $
$m \gets B^{d_1} \pmod{n_1} $
$m' \gets A^{d_2} \pmod{n_2} $ <-- I wonder if $m'$ is equal to $m$ as well?

Put 1 into 4; put 2 into 3, then

$$(M^{d_1} \;(\bmod{n_1}))^{d_2} \pmod{n_2} \equiv (M^{d_2} \;(\bmod{n_2}))^{d_1} \pmod{n_1} $$

Please kindly help if my concept is correct? Thanks!

I see you use the same generator on both sides (this need not work for any $n_1, n_2$ of course...). But even if this holds (trying a small example):

Let 1 use $n_1 = 11, M=2$, and 2 uses $n_2 = 13, M= 2$. Check that $2$ is a generator for both of the multiplicative groups.

If $d_1 = 7, d_2 = 9$, then $A = 2^7 \bmod 11 = 7$, while $B = 2^9 \bmod 13 = 5$.

But $5^7 \bmod 11 = 3$ which does not equal $7^9 \bmod 13 = 8$.


AES-GCM conformance test Is there any conformance tests/sequences to validate AES-GCM & GHASH() implementation?

Details: I'm implementing AES-GSM, that's just for better understanding of that stuff, nothing more. Well I need to validate somehow my result. There is 'openssl' and some python libraries to do encryption but they allow to check only final encryption result and nothing else in between. I haven't seen anything at all to validate 'GHASH()' or 'multH()'.

Thanks.

gcm-spec, this document has "AES Test Vectors" section in the end. There are a numerous test cases with all intermediate results for encryption and ghash. I found them a rather useful.


SHA1 calculation for millions of strings having common prefix I have a function in which I need to calculate SHA1(common_prefix + random_string). I am calling this function many times so that calculation of SHA1 slows down the performance of the function. As for the all of the calls, I am using a common_prefix, is it possible to tweak SHA1 in a way that it won't calculate the hash for the (common_prefix+random_string), however it does something like a preprocessing for (common_prefix) and using this preprocess(calculated values) to calculate SHA1(common_prefix+random_string)?

Is it somehow possible to do it?

Yes, you can save effort, if the common prefix is at least one 512-bit block.

Speaking mathematically: For a padded message $m = m_1 \mathbin\| m_2 \mathbin\| \cdots \mathbin\| m_\ell$ of $\ell$ 512-bit blocks, $$\operatorname{SHA1}(m) = f(\cdots f(f(\mathit{iv}, m_1), m_2) \cdots, m_\ell),$$ where $f$ is SHA-1's internal compression function.  For example, suppose you have a pair of two-block messages $m_1 \mathbin\| m_2$ and $m_1 \mathbin\| m_2'$ with a common prefix $m_1$ and distinct suffixes $m_2$ and $m_2'$.  Then

\begin{align}
  \operatorname{SHA1}(m_1 \mathbin\| m_2) &= f(f(\mathit{iv}, m_1), m_2), \\
  \operatorname{SHA1}(m_1 \mathbin\| m_2') &= f(f(\mathit{iv}, m_1), m_2'),
\end{align}

which share the common subexpression $f(\mathit{iv}, m_1)$.  If you precompute $h_0 = f(\mathit{iv}, m_1)$, then you can more quickly compute $\operatorname{SHA1}(m_1 \mathbin\| m_2) = f(h_0, m_2)$ and $\operatorname{SHA1}(m_1 \mathbin\| m_2') = f(h_0, m_2')$.

Speaking programmatically: Most implementations of SHA-1 support an init/update/final API.  For example, to hash the string hello world with OpenSSL's API you might write:

SHA_CTX ctx;
unsigned char h[20];

SHA1_Init(&ctx);
SHA1_Update(&ctx, "hello", 5);
SHA1_Update(&ctx, " ", 1);
SHA1_Update(&ctx, "world", 5);
SHA1_Final(h, &ctx);

The state of the SHA-1 computation, including buffering to split messages into blocks, is stored in the SHA_CTX object.  In some cases, like in OpenSSL, you can copy the context in order to save any effort that had already been done to hash what you've fed into it so far:

SHA_CTX ctx, ctx0, ctx1;
unsigned char h0[20], h1[20];

SHA1_Init(&ctx);
SHA1_Update(&ctx, "Once before a console dreary, while I programmed, weak and weary", 64);

ctx0 = ctx;
SHA1_Update(&ctx0, "\nOver many a curious program which did TECO's buffer fill...", 60);
SHA1_Final(h0, &ctx0);

ctx1 = ctx;
SHA1_Update(&ctx1, "\nO vermin yak urea's pro-Grammy itched dt casbah fur fell...", 60);
SHA1_Final(h1, &ctx1);

The resulting hashes are

h0 = b2b36d39d4431b3a57b7c30630bbbde9553b50ae
h1 = 2a0dae0548307b4ef33c0f1fedd7cbad2c32d5d8