texts:
The standard Salsa20 core is a $\{0,1\}^{384} \to \{0,1\}^{512}$ random function with a 16 byte constant ($\sigma$ for a 32-byte key), an 8 byte nonce, an 8 byte counter, and a 32 byte key. The hash function does not make any distinction between the types of input. This leaves 48 bytes which can be randomly chosen. If they are all chosen randomly and are kept secret, does that increase the keyspace to $2^{384}$, or is there some reason why the internal state of the cipher is limited to 256 bits? I ask this because the Linux kernel random driver (called CRNG) uses ChaCha20 to generate randomness.

The cipher state is initialized in the Linux kernel with the following function:

static void crng_initialize(struct crng_state *crng)
{
    int             i;
    unsigned long   rv;

    memcpy(&crng->state[0], "expand 32-byte k", 16);
    if (crng == &primary_crng)
        _extract_entropy(&input_pool, &crng->state[4],
                         sizeof(__u32) * 12, 0);
    else
        _get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
    for (i = 4; i < 16; i++) {
        if (!arch_get_random_seed_long(&rv) &&
            !arch_get_random_long(&rv))
                rv = random_get_entropy();
        crng->state[i] ^= rv;
    }
    crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
}

The state, kept in (struct crng_state *)crng->state, has the constant $\sigma$ for the first 16 bytes, and the last 48  bytes are generated randomly using _extract_entropy(), a function that returns the amount of entropy requested. Does this mean CRNG output has a $2^{384}$ keyspace?

If there is an attack against ChaCha20 that requires at least $2^{256}$ invocations of the cipher, then increasing the keysize does not increase security (even if 256 is already plenty). In other words, ChaCha20 with a 256-bit key is 256-bit secure, but I do not know if ChaCha20 with a 384-bit key is 384-bit secure. Would there be no attack faster than brute force for a 384-bit key?

I am fully aware that even a good 256-bit cipher is considered impossible to break with modern technology and that there is no practical reason to use a larger key. However sometimes it is useful to know how much entropy is present in a given amount of pseudorandom data.


texts: Does this algorithm have a name? (Distance between letters)

texts:
This came to mind the other day and I'm wanting to know if there is a name for the following algorithm (I'm not sure if "cipher" is the right word for it):

Take two consecutive letters at a time (not just one).
Perform the A1Z26 cipher on each letter to get their position in the alphabet as numbers.
Take the difference between those numbers obtained in the previous step.
Convert the difference back into a letter through A1Z26 in reverse. If the difference is positive, use a capital letter. If the difference is negative, use a lowercase letter. If you encounter two of the same letter in a row (difference is 0), convert them to the letter Z, since there is no "0th" letter of the alphabet, and Z would otherwise go unused since we're taking differences (the maximum difference possible would be Z - A -> 26 - 1 = 25 -> Y). Z is always capitalized.
Repeat until you reach the last letter, in which case you "wrap" back around from the last letter to the first.

"Hello world", for example, becomes "CgZcG HcFHs"

H, e -> 8 - 5 = 3 -> C
e, l -> 5 - 12 = -7 -> g
l, l -> 12 - 12 = 0 -> Z
l, o -> 12 - 15 = -3 -> c
o, H -> 15 - 8 = 7 -> G
w, o -> 23 - 15 = 8 -> H
o, r -> 15 - 18 = -3 -> c
r, l -> 18 - 12 = 6 -> F
l, d -> 12 - 4 = 8 -> H
d, W -> 4 - 23 = -19 -> s

Is there a name for this method, or a similar algorithm? What are other examples of algorithms working on not the individual letters themselves, but mathematical operations between 2+ letters?


texts: How do zero knowledge protocol with vertex-3-coloring work?

texts:
I'm currently not sure if I understood how the zero knowledge protocol with vertex-3-coloring works. I'll describe what I think I've understood and I'll write my questions in bold.

Zero-knowledge-protocols in general

What are they good for? What is a typical scenario?

I think they are good for authentication (The verifier wants to authenticate the prover):

The prover sends a graph for which he knows know a three-coloring to the verifier. They have to be sure that an attacker can't change this graph before the verifier gets it.
When the verifier wants to authenticate the prover, she asks for the colors of the vertices of one edge:

The prover chooses a permutation for colors
The prover applies this permutation the his coloring
The prover sends the permutated colors of the two vertices of one edge to the verifier

The verifier repeats step 2 as often as she wants.

I've found a good interactive example where you can play this game.
This site includeas another question:

[...] but also raises the question whether or not the prover is just outright cheating

How can I be sure that the prover actually has a three-coloring?

e.g. lets assume that the prover always answers (red, blue) for any request of the verifier. What would go wrong?

(After reading this great example I think there has to be some probability-part that I currently miss)

Vertex 3-coloring

How can the prover efficiently generate a big graph with a valid three coloring? How can he make sure that it is actually difficult to get a three coloring for this graph?


texts: Memory hard key derivation (password hash) using AES encryption

texts:
I am restricted on a certain environment involving PHP and am currently unable to implement new memory hard hashes such as scrypt (and I am not trying to compete with the likes of scrypt).

My current key derivation is simply an iteration of HMAC (password + salt). But it seems that using AES or other encryption ciphers, one could construct a fairly simple, memory-hard key derivation function using build-in PHP capabilities such as HMAC and AES encryption (assuming PHP is compiled with openssl support).

Pseudocode is:

salt = random (any length between 512bit and several MB)
M[0] = HMAC (sha512, password, salt)

for i=1 to N
    hash = HMAC (sha512, M[i-1], M[0] + i)
    M[i] = AES-128-CBC (iv = substr(hash,0,128), key = substr(hash,128,128), data = salt + hash) // substr lengths in bit

result = M[N]

for i=0 to N
    result = HMAC (SHA512, result XOR M[i], M[N-i])

Because of the second for loop, the entire matrix M needs to be present in memory, which would hopefully make it memory hard. Then one could configure salt size versus N to see what gives the desired results of memory usage and cpu usage within a reasonable amount of time.

I would appear to me that AES related-key attacks are not an issue in this scheme also because of the second for loop which hashes all matrix elements. The purpose of using AES is to obtain a larger randomized text for each array element than a 512 bit hash output would be. Since iv and key are unique and are related only through HMAC hashing, this use of AES would also appear to be secure. Even so, I appreciate your input. Creating one's own crypto is not encouraged, which I understand. Even if I do not end up using this, your feedback would really help me improve my understanding of these matters.

Also, I wonder whether the length of the salt affects the security of the function? I.e. if the salt were to be very long, say several MB, would that make it less safe than if the salt was short such as 512 bit (less reliance of encryption, more HMAC hashes)?

EDIT:

For theoretical purposes and NOT in order to create my own cryptography, based on the comments of otus, it appears that in principle, higher memory-hardness is achieved by a more intense shuffling of the matrix.

Therefore, one could e.g. generate a matrix of a size rounds * x, which is then hashed rounds times, but each hash made up of XOR-ring x*2 matrix values. The example below (PHP code) shows it for x=4 (^ is the PHP XOR operator):

for ($i = 1; $i <= $rounds; $i++) {

    $result = hash_hmac ('sha512',
                $result . ($matrix[$i] ^ $matrix[($rounds+$i)] ^ $matrix[($rounds*2+$i)] ^ $matrix[($rounds*3+$i)]),
                ($matrix[($rounds-$i)] ^ $matrix[($rounds*2-$i)] ^ $matrix[($rounds*3-$i)] ^ $matrix[($rounds*4-$i)]));

}

For 8 rounds, a matrix size 8*4 = 32 would be created, and then hashed with XOR combinations in the loop shown. The output below shows, which matrix index values (the $i in $matrix[$i]) would be combined in each HMAC round:

Computing 1 ^ 15 ^ 17 ^ 31 AND 7 ^ 9 ^ 23 ^ 25
Computing 2 ^ 14 ^ 18 ^ 30 AND 6 ^ 10 ^ 22 ^ 26
Computing 3 ^ 13 ^ 19 ^ 29 AND 5 ^ 11 ^ 21 ^ 27
Computing 4 ^ 12 ^ 20 ^ 28 AND 4 ^ 12 ^ 20 ^ 28
Computing 5 ^ 11 ^ 21 ^ 27 AND 3 ^ 13 ^ 19 ^ 29
Computing 6 ^ 10 ^ 22 ^ 26 AND 2 ^ 14 ^ 18 ^ 30
Computing 7 ^ 9 ^ 23 ^ 25 AND 1 ^ 15 ^ 17 ^ 31
Computing 8 ^ 8 ^ 24 ^ 24 AND 0 ^ 16 ^ 16 ^ 32

One concern there is the question of whether that many XOR operations would create a lot of of collisions and thus somehow security, even though each result is HMAC hashed. It would be interesting to get people's comments on that, with the reasons behind it.


texts:
I wonder if someone can give an explain about the different between two Diffie-Hellman Primitives defined in SP800-56A, CH5.7.1

5.7.1.1 Finite Field Cryptography Diffie-Hellman (FFC DH) Primitive
5.7.1.2 Elliptic Curve Cryptography Cofactor Diffie-Hellman (ECC CDH) Primitive

Actually the first one is named as (FFC DH) and its looked very similar to RSA way.
And for the 2nd one , though it is based on ECC, but is also on a Finite Field.


texts: Using the same secret key for encryption and authentication in a Encrypt-then-MAC scheme

texts:
Is it a weakness to use a single shared secret for protecting messages using a Encrypt-then-MAC scheme?

Assuming a system is using AES-256-CBC and a SHA1-HMAC and the same secret key for both operations.  Upon intercepting one of these messages and attacker could brute force this secret key by trying to solve the HMAC or by successfully decrypting the first block of the ciphertext.

Performing  a decryption on a single block of AES-256 should be a lighter operation than performing a SHA1-HMAC on a potentially large message.  Therefore AES-256 is ideal for a massively parallel brute-force attack and the use of the SHA1-HMAC doesn't hurt the system.

Is this approach sound, or is there an attack that has not been taken into consideration?


texts: Generating cyclic group for Ciphertext-Policy Attribute-Based Encryption

texts: I am doing Project under the topic CP-ABE.I need to generate a symmetric bilinear group Go of prime order p and with generator g...Then how to choose random elements from Zp....kindly anyone help me...Is it possible to do this with Java?


texts: Finding $x$'s parity in the discrete log problem

texts:
Suppose $p$ is prime, and $g, a\in\mathbb F_p$ are given elements with $g$ a primitive root. The discrete log problem poses the task of finding an integer $x$ such that $g^x=a$. Show that even if $x$ cannot be recovered, one can check if $x$ is odd or even by inspecting the element $a^{(p-1)/2}$.

I'm not sure how to approach this question. I tried $g^{x(p-1)/2} = a^{(p-1)/2} = 1$.

Any help would be appreciated! Thanks.


texts: Severity of Cooking NIST P Curve Constants

texts:
Bruce Schneier and Gregory Maxwell have both stated that they believe the constants chosen for NIST's P curves (i.e. P-256r) are cooked. DJB has put together a detailed list of red flags but, outside of the suspicious constant, everything else appears to be potential implementation issues.

What kind of a speedup could they gain from cooking the constant?

Note: I'm aware of related questions, I'm looking for more of a high-level takeaway.


texts: What's the difference between digest algorithm and signing algorithm?

texts:
I'm reading rfc5652, there are different references of the two algorithm identifiers.
For example in this ASN.1 structure:
SignerInfo ::= SEQUENCE {
        version CMSVersion,
        sid SignerIdentifier,
        digestAlgorithm DigestAlgorithmIdentifier,
        signedAttrs [0] IMPLICIT SignedAttributes OPTIONAL,
        signatureAlgorithm SignatureAlgorithmIdentifier,
        signature SignatureValue,
        unsignedAttrs [1] IMPLICIT UnsignedAttributes OPTIONAL }

There're two types of identifiers: DigestAlgorithmIdentifier and SignatureAlgorithmIdentifier.
When using RSA for signing; isn't the digest algorithm represents the hash function used to compute the hash value, that's encrypted using the private key?
What's the signing algorithm in this case?


texts: Hash into elliptic curves for private set intersection

texts:
Would it be insecure to hash a message $m$ to an elliptic curve point by multiplying it to some generator $G$ for the purpose of a private set intersection ?
$$
M = hash(m) * G
$$
I keep seeing references that hashing with $M = hash(m) * G$ might be dangerous :

How to Hash into Elliptic Curves, Thomas Icart

Deterministic Hashing to Elliptic and Hyperelliptic Curves, Mehdi Tibouchi

Efficient Indifferentiable Hashing into Ordinary Elliptic Curves, Thomas Icart

hash - Fast hashing into elliptic curve - Cryptography Stack Exchange

the discrete logarithm of $h(m)$ with respect to $G$ is known , which makes most protocols insecure.

However in the case of a private set intersection we can use a secret key $s$, so if I am correct the discrete logarithm of $h(m) *s$ would not be known :
$$
M_s = h(m) * s * G
$$
Private Set Intersection
In the case of a private set intersection Alice and Bob each have a secret key ($s_A$ and $s_B$) and lists of data. To see what data they have in common they encrypt their data twice (once with each secret key) and search for the matches. In this example Alice has the message $m_1$ and Bob the message $m_2$.

Alice computes $M_{1,A} = M_1 * s_A = h(m_1) * s_A * G $
Alice sends $M_{1,A}$ to Bob
Bob computes $M_{1,AB} = M_{1,A} * s_B$ and $M_{2,B} = M_2 * s_B$
Bob sends $M_{1, AB}$ and $M_{2, B}$ to Alice
Alice computes $M_{2, BA} = M_{2, B} * s_A$
If $M_{2, BA} = M_{1, AB}$ then $M_1 = M_2$

In summary we test if
$$
h(m1) * s_A * s_B * G = h(m2) * s_A * s_B * G
$$


texts:
Picture a simple substitution cypher of text with length $N$(spaces optional):

Plain    : ATTACK AT DAWN
Encrypted: ELLETI EL HEPG

Another way to represent the encrypted text is with an $N \times N$ matrix $P$ of $0$s and $1$s:

$P_{ij} = 1$ if the $i^{th}$ character is the same as the $j^{th}$ character
$P_{ij} = 0$ if the $i^{th}$ and $j^{th}$ characters are different
$P_{ij} = P_{ji}$

So the encrypted text in the example above can be represented with the following matrix:

  E L L E T I _ E L _ H E P G
E 1 0 0 1 0 0 0 1 0 0 0 1 0 0
L 0 1 1 0 0 0 0 0 1 0 0 0 0 0
L 0 1 1 0 0 0 0 0 1 0 0 0 0 0
E 1 0 0 1 0 0 0 1 0 0 0 1 0 0
T 0 0 0 0 1 0 0 0 0 0 0 0 0 0
I 0 0 0 0 0 1 0 0 0 0 0 0 0 0
_ 0 0 0 0 0 0 1 0 0 1 0 0 0 0
E 1 0 0 1 0 0 0 1 0 0 0 1 0 0
L 0 1 1 0 0 0 0 0 1 0 0 0 0 0
_ 0 0 0 0 0 0 1 0 0 1 0 0 0 0
H 0 0 0 0 0 0 0 0 0 0 1 0 0 0
E 1 0 0 1 0 0 0 1 0 0 0 1 0 0
P 0 0 0 0 0 0 0 0 0 0 0 0 1 0
G 0 0 0 0 0 0 0 0 0 0 0 0 0 1

Now imagine there was noise during the transmission of the encrypted text and instead of having just $0$s and $1$s in the matrix above, we end up with real numbers $P_{ij} \in [0, 1]$ representing the probability of character $i$ being the same as character $j$ - higher $P_{ij}$ means more likely that $i^{th}$ and $j^{th}$ characters match.

Any ideas/references discussing attacks under the described conditions?

Edit: Consider $N > 200$ and the language of the plain text is known.


texts: Length extension attack SHA-1 message division with padding problem?

texts:
I'm was reading this example for length extension attack given here
link

When working out, how the extended block length be divisible by 512 (SHA block size).

I'm assuming following:-

In SHA, the size of the blocks is 512 bit.
The last block must contain:the rest of data in message (mod 512).
some filling (padding)
the last 64 bits as length

In example given in link shared above, this is what extended msg looks like

http://example.com/downloadfile=report.pdf%80%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%A8/../../../../../../../etc/passwd&mac=ee40aa8ec0cfafb7e2ec4de20943b673968857a5

Example 1
Calculating

A more precise of asking is that,
message =10 bytes = 80 bits
secret key = 11 bytes= 88 bits
168 mod 512= 160 bits= 21 bytes
64 - 21= 43
padding +message length= 464+552 =1016 bits
adding /../../../../../../../etc/passwd 32 x 8= 256 bits
Adding it to A8/=  424

How I make sense If I add the missing padding which is 256 mod 512 =256=32 bytes

64-32  = 32 x8= 256 bits

Example 2

count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x02\x28&waffle=liege

Going on by logic

message =55 bytes = 440 bits
secret key = 14 bytes= 112 bits
length encoding = 552
552 mod 512= 40 bits= 5 bytes
64 - 5= 59 bytes
If you check the padding its 58 bytes not 59 . Can you tell why?
padding +message length= 472+552 =1024 bits
adding extra &waffle=liege 13 x 8= 104
adding to existing message length(552) + 104= 656
How I make sense If I add the missing padding which is 656 mod 512 =144
= 18 bytes
64 - 18= 46 x 8 = 368 bits
104 + 368 (message length and padding)


texts: How to find the generator of an elliptic curve?

texts: If the elliptic curve has prime order of points, then all of its points are generator. Is this true? If so, how can I find the optimized generator(which generates more number of points) among them?


texts: Clarification on the origin of `01` in this oracle padding attack?

texts:
I have found what I believe to be a straightforward explanation of the oracle padding attack here: http://robertheaton.com/2013/07/29/padding-oracle-attack/

I am however getting confused by something which experts here should I believe find so easy.

When you open the link and browse to the subsection titled "Manipulating the Cipher text", there is a statement which says ...

  If the server says that we have produced a plaintext with valid padding, then we can be pretty sure that P2'[16] must be 01.

I am unable to understand why a value of 01 will imply that the padding is OK. I know that as per PKCS#5, the only way we can get 01 as the last byte is when there was only 1 byte of padding. But according to the example on this page, I don't see anything that suggests that the data had 1 byte of padding. So, I fail to understand why a result of 01 is considered successful.

Is anyone able to look at the document and advise where the 01 comes from?


texts:
How to calculate key size for Diffie-Hellman key exchange? The strength obviously depends on both generator and prime modulus.

  Formula:

  $$g^x\bmod p$$

  Public values:

  $$g=3$$

  $$p=17$$

  Alice:

  $$x=15$$

  $$3^{15}\bmod 17=6$$

  Bob:

  $$x=13$$

  $$3^{13}\bmod 17=12$$

  Alice:

  $$12^{15}\bmod 17=10$$

  Bob:

  $$6^{13}\bmod 17=10$$

The original numbers $(3,17,13,15)$ weren't that (no way secure, but not that) low and they ended up with 10 which is much easier to brute force than guessing each part from $g^x\bmod p$.


texts: usefulness of a collision attack that's not also a 2nd pre-image attack

texts:
So my understanding is that if we've got some hash function $H$ then a 2nd pre-image attack is one where given a message-hash pair $(m, H(m))$ we can find some $m' \neq m : H(m') = H(m)$, while a collision attack is to find any old $m, m'$ such that $H(m) = H(m')$.

Everywhere I see people talking about collision attacks it really seems that they mean 2nd preimage. What would be the usefulness of a pure collision attack where you have no control over $m$ or $m'$? There are all those results about how SHA-1 is broken w.r.t. collision attacks, but it seems that people really mean 2nd pre-image. Is this just a convention that people are not strict about, or am I missing something?

For example, in this SE question the author of the accepted answer gives an example of where a collision attack could be used to swap out malware for a valid Windows update. But to me that seems to be a 2nd pre-image attack, not a pure collision attack, because the attacker needs to ensure that the hash of the malware matches a particular hash, i.e. that of the Windows update.


texts:
I am going through the course http://u.cs.biu.ac.il/~lindell/89-856/main-89-856.html, as it has a good lecture notes. I found exercise 2 solution a puzzling statement: it says that $G^\prime (x_1 , x_2 ) := G(x_1 ) ⊕ G(x_2)$ is a PRG, though I'm not sure why it is always the case. I get the intuition that xoring pseudorandom string with another pseudorandom string is also pseudorandom, though the formal proof is unclear to me.

Is it also true to PRG with any stretch $l$?


texts: Simple RSA proof of correctness using Bézout's identity

texts:
To show that $m^{ed} \equiv m \pmod{pq}$ with $de \equiv 1 \pmod{\phi(pq)}$ and $p\neq{q}$,

Choose $e$ coprime to $\phi(pq)$ so that $\gcd(e,\phi(pq)) = 1$ and

$$m^{\gcd(e,\phi(pq))} \equiv m \pmod{pq}$$

Using Bézout's identity we expand the gcd thus

$$m^{\gcd(e,\phi(pq))} = m^{ed + \phi(pq)k} \pmod{pq}$$

where $d$ appears as the multiplicative inverse of $e$ and we expand the exponent

$$m^{ed + \phi(pq)k} = m^{ed} (m^{\phi(pq)})^{k} \pmod{pq}$$

By Fermat's little theorem this is reduced to

$$m^{ed} 1^{k} = m^{ed} \equiv m \pmod{pq}$$

which is the original claim.

Please review this simple proof and help me fix it, if it is not correct.


texts:
GAC consists of absolute indicator and sum of square indicator. Please help me in understanding what are these indicators? How to calculate GAC for Sbox?
What is confusion Coefficient Variance of an Sbox?


texts: Hashing a password before using for online accounts

texts:
I don't actually know what I'm talking about, so apologies if I get anything wrong. At the moment I have a password naming system for most of my online accounts that looks something like this: masterpassword + appname, where appname is the name of whatever service the password is for. ex. $sickpass123$_SoundCloud and $sickpass123$_Gmail. The idea is to have an easy to remember master password combined with the app name so every password is unique. I am worried though, because if a proactive individual manages to figure out one of my passwords, it would be easy for them to figure out the other passwords since they all contain the same master password.

I thought of running each password through a hash function (every time need to enter it) as this would ensure that each password is unique. ex. 8d9f24e142b33c2f7f3d59fc7c6043a7 and 84e08387ef918182154713d388f5ea62. In addition, I could encode the hash output in base64 or ascii85 to fulfill the capital letter/number/symbol requirements for passwords in online services. ex. OGQ5ZjI0ZTE0MmIzM2MyZjdmM2Q1OWZjN2M2MDQzYTc= and ODRlMDgzODdlZjkxODE4MjE1NDcxM2QzODhmNWVhNjI=.

I am also aware of password generators, but they generate a random string each time rather than a predictable output. I would rather have the same output be generated every time I enter my password. That way, it will be easy to remember every password, but the hash function will make each one virtually unique. Also, if only the hash output is given to websites, rather than the original password, the sites themselves will not know my pattern.

Is there any problems from using the approach I am suggesting?
Would it actually be less secure if the server encrypted my already encrypted password?
Should I encode the output in base64 or ascii85, or something similar?
Which algorithm would be best suited to this task? Do I need something more secure like SHA-1 or will the more primal MD5 be adequate (would anyone care enough to try to break the hash)?

EDIT: Thanks for all the answers. They were all very informative. I think I might try a password manager, perhaps MasterPasswordApp as @Matty suggested, as it'll be easier to manage.


texts: Is using a predictable IV with CFB mode safe or not?

texts:
While writing this answer, I noted that NIST SP 800-38A says that (emphasis mine):

  "For the CBC and CFB modes, the IVs must be unpredictable. In particular, for any given plaintext, it must not be possible to predict the IV that will be associated to the plaintext in advance of the generation of the IV."

For CBC mode, using a predictable IV allows a well known chosen plaintext attack exploiting the way in which the IV is combined with the first block.  However, I don't see how a similar attack could apply to CFB mode; indeed, as I observed in an earlier answer, the CFB, OFB and CTR modes are equivalent for the first block.

Indeed, in this answer, Thomas Pornin writes that (emphasis again mine):

  "CFB and OFB require only uniqueness: for a given key, each IV value shall be used at most once. The is no need for unpredictability or uniformness because the IV is first encrypted "as is" (before any operation with the plaintext) and encryption of a sequence of values with a good block cipher, using a key that the attacker does not know, is a good PRNG."

So, is Thomas wrong, or is NIST mistaken or merely excessively cautious?  And if there is an attack enabled by using predictable IVs with CFB mode, how does it work?


texts: How to perform Black box testing of a key exchange protocol?

texts:
Though obviously not an alternative for proper cryptanalysis, I was wondering about statistical/black box analysis. Should I produce a new key exchange protocol. With the same shape as Diffie-Hellman:

Each side picks a random number $r_i$, calculates $f(r_i)$ sends it and receives $f(r_{1-i})$ then calculate a shared key $g(f(r_{1-i}),r_i)$ = $g(f(r_i),r_{1-i})$

Obviously for the key exchange to be secure $f$ needs to be one way, I'm aware of NIST tests for PRNGs I assume they could be used to evaluate a one way function. Though obviously showing $f$ is a one way function isn't sufficient, what more can be tested empirically? Are there any existing sets of tests you can run?


texts: Scalar Multiplication on Elliptic Curves

texts:
In the elliptic curve: $y^2 = x^3 + 20x + 13 \bmod{2111}$.
Using the point $P=(3, 10)$

I am wondering how to multiply this point by the scalar $57$?

I realize I can write $57*P$ as $2^5*P + 2^4*P + 2^3*P + P = 2(2(2(2(2P)))) + 2(2(2(2P))) +2(2(2P)) + P$.

My question is what is the best way to calculate these doubles and additions?

Some pseudo code or real code would be greatly appreciated although even a tutorial on how to do this by hand would help a lot!


texts: Encryption of numeric value using playfair

texts:
I am studying in CSE and in my recent exam paper, A question was asked as:

Construct a playfair cipher for Plaintext: semester5 and key:technology.

Generally as we are taught yet, there is no example of playfair matrix substitution for numeric value.

So, what to do with number 5? Is there any trick for this kind of encryption?


texts: Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR

texts:
Suppose that we have a sequence of $N$ digits which is produced by a Linear Feedback Shift Register (LFSR) and the shortest such LFSR is of length $L$. A very important tool in cryptanalysis of stream ciphers (among many other things) is the Berlekamp-Massey algorithm; if $2L\leq N$, this algorithm will produce the unique shortest LFSR of length $L$ that generates the given sequence.

I just knew this as a fact but never really gave a look at the algorithm. Now I'm reading the paper by Massey that presents the algorithm and I was kind of surprised to realize that the algorithm returns a desired LFSR in any case, even if $2L>N$, however in that case we don't have a unique LFSR that generates the sequence, but $2L-N$ of them (in the binary case).

So why do we always refer to the Berlekamp-Massey algorithm only for the case when $2L\leq N$? Practically speaking, what kind of lengths $L$ do we use in cryptosystems, and can the algorithm be used when $2L>N$ and $N$ is "reasonably" close to $2L$? Or is the algorithm useless in that case regardless?


texts: Are there transitive ciphers (either symmetric and asymmetric)

texts:
Say Alice has information that's already encrypted with Bob's key.
She wants Bob to decrypt it without knowing what he just decrypted.
So she encrypts it with her key and sends it to him, he decrypts with his key, and sends it back and she decrypts it with her key.

Is there a block cipher where this would work?


texts: Technical term for hash value being uncorrelated to input message?

texts: Is there a technical term for the desirable property of hash functions. That a small change to the input message will produce a massive unpredictable and seemingly uncorrelated change to the output hash value? I keep getting stuck on words like pseudo-random and unpredictable but they don't seem to fit the property correctly.


texts: Reverse MD5 of a 76 character string when the first 44 characters are known

texts:
I have a situation where I would like to reverse a hash which is the MD5 of a concatenation of 76 characters. I know the first 44 characters but don't know the remaining 32 characters. A description of the problem is as follows:

Hash = MD5 (cat (known_string_of_length_44chars, unknown_string_of_length_32chars))

I can generate Hash values for multiple combinations of the known_string. I would like to determine the unknown_string. Can this be done? Is brute forcing a possibility?


texts: Can a LIRA system work with cjdns or other decentralized meshnets?

texts:
LIRA (Lightweight Incentivized Routing for Anonymity) is a scheme to incentivize participants in Tor to contribute resources, in particular bandwidth.

The paper talks about it being used for Tor. Can it work for other decentralized and privacy-friendly networks as well, such as cjdns?


texts: Currently I'm working on implementing a seed/key algorithm to limit access to a tool for authorized users. My understanding of the algorithm is that its strength is derived from the seed itself. However the majority of articles say "The basic idea is that the server provides a seed -- a short string of byte values -- and the client is required to transform that seed into a key using a secret algorithm." If the algorithm's security is based on the seed, why is it "a short string of byte values" instead of the longest possible string of byte values?


texts: Motivation for the definition of statistical distance

texts:
Statistical distance is a widely used measure in cryptography for comparing two distributions. One can define various other measures for capturing the differences between two distributions, but why do we prefer to use statistical distance? What is the physical significance of statistical distribution definition, which goes as follows:

Let $X_1$ and $X_2$ be random variables with domains $D_1$ and $D_2$, then the statistical distance between $X_1$ and $X_2$ is defined as:

$\delta(X_1,X_2) = \dfrac{1}{2}\sum\limits_{x \in D_1 \cup D_2}|Pr(X_1 = x) - Pr(X_2 = x)|$

I found this definition in the second chapter of the textbook titled "Secure Multiparty Computation and Secret Sharing".


texts: What do you call one time pad where pseudo-random numbers are used?

texts: What is the encryption method called when pseudo-random numbers are used instead of true random numbers?


texts: How can the 'randomness' of a finite sample of binary keys from a finite key space be estimated?

texts:
Given a set of bit sequences generated by an extractor, what would be a valid setting for estimating the
randomness of these generated keys and what resolutions can be drawn for
that extractor in general? The extractor will only generate bit sequences of fixed length such as 20 bits. Thus, all possible outcomes span only a finite key space.
Randomness
Though we would like to take the generated sequences as input to a cryptographic protocol (which has strong security properties even in the case of low-entropy input)
our requirements for 'randomness' are somewhat less strict than in any well-defined notion of randomness since these typically focus on properties of infinite sequences.
We are rather focusing on local randomness, i.e. the properties expressed by finite subsequences of random sequences of infinite length, and we would be even comfortable with results characterizing the peculiarities/bias/inter-bit-dependencies
our extractor exhibits.
Currently, we approach this problem from two angles:

Empirical: We apply statistical tests on the set of generated sequences such as comparing the number of birthday collisions in the set of sequences with the estimated number of collisions for a typical sub sample of same size. We should point out here that we are aware of suites as dieharder, but don't think they are applicable here as we are only interested in the case of finite sequences.
Conceptual: We focus on corner-cases such as the case where our extractor produces the sequence consisting exclusively of ones and reason about the likelihood of this event.

Please Note: We are aware of suites such as dieharder. We also know about different other tests but consider them not applicable here as they do not focus specifically on sets of fixed-length sequences!
Though we think there is no other straight-forward way of solving this question, we would be grateful for any further insights or advices. Meaningful tests would also be much appreciated.
Update: While we know that concatenation of these bit sequences should be possible given they are random, we inherently lack enough data to do so - we depend on specific sensor data for our extractor to work and this is not easy to obtain in large amounts. We might be able to extract only about 1GB. Therefore, we are trying to bypass this lack of data by focusing more on the specific characteristic of our problem.
Also, the term key is probably not applicable here and should be taken as password instead as we do not ever use it to encrypt plain text. This might enable us to use it even if there are some known slight weaknesses in the extractor.


texts: How exactly would someone attempt to analyse ciphertext produced by popular encryption products such as Truecrypt/PGP?

texts: I am interested in understanding what the process would be if an attacker wished to attempt to decrypt data secured by common tools such as OpenPGP, Truecrypt or the like. Are there any documented records of such undertakings, or papers I can read to understand how a cryptanalyst approaches breaking an implementation? What would happen to break such a system? Can such systems be brute forced realistically?


texts:
Good day to everyone.

I am trying to implement an e voting system (just for reference -it is not important though-it is described at the Internet Voting Protocol Based on Improved Implicit Security by Abhishek Parakh & Subhash Kak Version of record first published: 29 Jun 2010. ).

The protocol I am trying to implement mentions that "The Polling Station verifies the validity of Voter-id by conducting a zero-knowledge challenge-response protocol with the Registry Authority to validate the signature of voter-id."

I have searched at Google, and at Wikipedia about this protocol, but I didn't get much information. It is very important for me, to learn about what is this protocol, and what Polling station has to sent to Registry Authority, and what Registry Authority has to send back. Basically, I need to know how I can achieve to validate the voter-id.

Thank you very much for your time.

Ps. I just created account at this forum. If you need to provide you with any further information please ask it, and I will answer.


texts: What is a white-box implementation of a cryptographic algorithm?

texts:
What is a white-box implementation?

Does a white-box implementation have specific properties?


texts: Is the complexity of Pollard rho for discrete logartihm really the modulus?

texts:
so I'm reading everywhere that the Pollard Rho for Dlog's complexity of $g^a \pmod{n}$ is $\mathcal O(\sqrt{n})$.

Shouldn't it be $\mathcal{O}(\sqrt{q})$ with $q$ the order of $g$?


texts: Fully homomorphic encryption arbitrary functions formulation

texts: I am currently studying the interesting field of homomorphic encryption. I read that from a fully homomorphic encryption function that supports both addition and multiplication you can perform any mathematical and comparison operations. Ok, but how can you do this specifically? How do you for example perform comparisons ==, <. >= or exponential operations? How about floating number operations?


texts: Frequency of letters change by the length of the texts?

texts:
In terms of the frequency of letters, how is it possible to have different frequent letters when the length of the text I'm analyzing is shorter?

At the moment, I'm comparing the frequencies of a long text and a subtext from that text. To my surprise, the most frequent letters changed. In the long one it was the letter e followed by the letter t, however in the small text it was t followed by e. Also, when I checked the frequency of different types of texts (e.g news articles), the frequency of letters also changed as well as the most frequent one.

The bottom line is, how can that be possible? It makes no sense to me.


texts: Is this correct/incorrect password for file encryption scheme secure?

texts:
I'm writing an AES file encryption program, and I'd like to put in a way to tell whether or not the user has entered the correct password without decrypting the entire file and GCM telling me the tag is invalid.

My process is as follows:

Get the user to enter a password ($p$), generate a salt/nonce/IV ($n$), and use Scrypt to generate 2 keys (The first and second half of the generated key); $$k_1, k_2 = Scrypt(salt:n, keylen:32, n:2^{16}, r:8, p:1).derive(p)$$
Encrypt the data of a file with $\text{AES-GCM-128(}k_1, \text{iv/nonce=n})$ and empty associated data.
Write encrypted data to the file so that the contents of the file is
$n || gcmtag || data$

Would it be secure if I instead wrote the following to the file:
$$n || gcmtag || k_2 || data$$

That means I can load $n$ from the file, take the user-inputted password, derive the keys, and check if the value of $k_2$ is equivalent to the $k_2$ loaded from the file.


texts: Is the DES F-function injective for a given subkey?

texts:
Is it possible for two different half-block inputs to the DES F-function, with the same round subkey, to produce the same output?

That is, if we feed two different half-block inputs $b_1$ and $b_2$ through the expansion stage, XOR them with a constant subkey $K$, and then pass the expanded and XORed inputs through the S-boxes, is it possible for the outputs $o_1 = F(b_1, K)$ and $o_2 = F(b_2,K)$ to be equal?


texts:
Cryptomania is usually presented as the Impagliazzo's world, which gives us public-key cryptography under the assumption that trapdoor OWFs exist.
For purposes of constructing public-key cryptography we also want the underlying problem to be in $NP \cap coNP$ as described in here.
Are there any papers, which explore this particular requirement in relation to Impagliazzo's worlds?
Edit 02/04/2021: After some more digging I managed to find the answer, which describes the $NP \cap coNP$ requirement, as such I am restructuring this question, to only ask about results on impagliazzo's 5 worlds in relation to this property.


texts: Does the time to evaluate a hash function depend on the function input size?

texts: Suppose we have a (variable-input size) hash function modeled as a random oracle. Can it be consistent to say that the time to evaluate this function depends on the input size ?


texts: Is it possible to construct a compression function that works exactly as MD5's CF but is much easier to compute?

texts: Is there any chance that MD5's compression function can be represented in a completely different way so that it's much easier to compute/reverse it?


texts: How to calculate the bias of cryptographic hash output from biased input?

texts:
Assume that I have a hardware entropy source.  Not a TRNG, but the source that might feed a TRNG's extraction algorithm.  This source produces independent bits with a not unreasonable bias of $60/40$.  So that's $p(1) = 0.6$ and $p(0) = 0.4$ and min. entropy would therefore be 0.737 bits/bit.

I then use a cryptographic hash function to extract entropy. Let's say I take groups of 320 bits from my entropy source and hash them with SHA1. What is the resulting bias in the long run output? Or how might this be calculated?

I'm hoping for a numeric answer or calculation rather than verbiage.


texts: Is there a mental poker algorithm that does not rely on commutative encryption?

texts:
The algorithm for mental poker that I saw on Wikipedia and everywhere else relies on an encryption algorithm such that $E_k(E_j(P)) = E_j(E_k(P))$, but I can't find a modern and secure algorithm for which this is true. The only algorithm I found with this property is SRA (I believe that's what it's called) but it relies on modular exponentiation, which is slow and resource intensive compared to a more common algorithm such as AES, not to mention less secure.

Is there a mental poker algorithm that doesn't rely on this property?


texts:
I am a programmer familiar with C/C++ and Python. Lately, we got an assignment from a team asking us to work on one of their projects: we need to make a small program to encrypt a large file using symmetric key encryption. We could easily achieve this using AES128 or AES256 in CRT mode.

The catch however is that if a small part of the file is given along with the location of that bytes from the beginning of the file we should be able to decrypt just that piece.

We thought cutting the file into multiple pieces and applying separate generated key for each but the issue is that regarding what we can do if the said part is not exactly a slice of the size we cut it into. Also would like to know if two over lapping such blocks can be handle.

The idea we are currently working on is this:

We are slicing into 128 bytes each.
Calculate number of bytes from the last slice. So if we get bytes from 10 to 128. It will be 9.
Generate a random padding of 9 bytes at the beginning and then decrypt it. Then remove the first 9 Bytes.
In case multiple slices overlap they are split and the method is repeated.

So, what I would like to know is if this is sensible or if there's a better cipher or algorithm that allows this.

PS:

The files will be image files or document files.
Only know some basics of cryptography.


texts: Confusion about security of quantum key distribution

texts:
In Quantum Key distribution, it is my understanding that when Eve tries to intercept photons being sent from Alice to Bob, she has a 50% chance of using the correct polarization filter, and so 50% chance of getting the correct bit information. Let's just say hypothetically that she somehow gets all the photons she intercepted using the correct filter (and hence correct bit information), and re emits them so that they're all exactly the same photons as Alice had intended them to be.

Doesn't this mean that during the error reconciliation between Alice and Bob, they'll detect no errors and hence conclude that the distribution of the key was secure, but in reality, Eve has perfect information about the "secret" key?
Doesn't this violate the proof that QKD is "provably secure"?


texts: I'm trying to understand the nature of true randomness. I'm building an RNG using a radioactive source. Basically, I'm measuring the time between consecutive decays which in theory should be unpredictable. The distribution of these time measurements shows a Gaussian-like distribution as I predicted. Now my understanding of true randomness requires a uniform distribution of variables, which is all variables are equally likely. How can I transform a Gaussian Distribution to uniform distribution and is it really necessary to have uniformly distributed random bits to have a good generator?


texts: Cryptopals challenge - not understanding the padding details

texts:
I am working on some tasks in Crypto, specifically on this small task: https://cryptopals.com/sets/2/challenges/9, which I aim to implement in Python.

The point is to add padding for a certain number of bytes, and the value of each byte is the number of bytes added. The example given is "YELLOW SUBMARINE\x04\x04\x04\x04".

I have solved this task I think, but the output is non-displayable. Here is one clean solution I found online

def pad_pkcs7(buffer, block_size):
    if len(buffer) % block_size:
        padding = (len(buffer) / block_size + 1) * block_size - len(buffer)
    else:
        padding = 0
    # Padding size must be less than a byte
    assert 0 <= padding <= 255
    new_buffer = bytearray()
    new_buffer[:] = buffer
    new_buffer += bytearray([chr(padding)] * padding)
    return new_buffer

buffer = bytearray("YELLOW SUBMARINEX")
print str(pad_pkcs7(buffer, 20))

When I run this I get the same result as with my own solution:
YELLOW SUBMARINE[?][?][?][?] (the []s are actually boxes with question marks in them)

My questions:

Why is the padding hex encoded in the first place? Why not YELLOW
SUBMARINE4444? Odd that it is part ASCII and part hex
Did this solution actually solve the problem? Should not the hex-encoded
version of 4 be quite possible to display as 4, 04, \x04?


texts: Subgroups generators with respect to group generators of composite order

texts: If I have a group $\mathcal{G}$ of order $N=npq$ and subgroups $\mathcal{G_n,G_p,G_q}$ of order $n$, $p$, $g$ respectively and if $g$ is a generator of $\mathcal{G}$ why then $g^{nq}$ is a generator of $\mathcal{G_p}$, $g^{np}$ is a generator of $\mathcal{G_q}$ and $g^{pq}$ is a generator of $\mathcal{G_n}$ ? I am trying to understand a research paper


texts: Randomized algorithms and the one time pad

texts:
The way I understand it, an algorithm is said to be randomized if it uses randomness as part of its logic (quoting Wikipedia). Now, in the case of encryption algorithms, I assume this means that for the same input, different outputs (i.e. ciphertexts) will be produced. The question is, what does "input" mean in this context?

In particular, does it include only the plain text to be encrypted, or does it also include the key? To give a concrete example, is the one time pad a randomized algorithm? If it is so, then "input" must mean plain text only.

To make matters more confusing (to me at least), again quoting Wikipedia: "To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.", where the last word is linked to the "Randomized Algorithm" page I link to in the first paragraph. So, given that the one time pad is semantically secure, is must be a randomized algorithm... right?

To add the cherry at the top of the confusion cake, there are still algorithms like, for instance, AES in CBC mode with a random IV, which will produce different outputs, when run multiple time with the same plain text, and the same key. Of course, this means that when you consider the input to one such algorithm as being the plain text only, you get the same result: different ciphertexts for the same plain text. So it would seem that the only "coherent" (lacking a better word) definition would require that input == plain text. Am I surmising correctly?


texts: Vigenere ciphertext encrypted with another vigenere cipher

texts: I have been learning about Vigenere ciphers and then thought of this scenario: if a cryptographer encrypts a plaintext English message with a Vigenere cipher and then another cryptographer, who wants to ensure that the message is very secure, encrypts the ciphertext with another Vigenere cipher (with a different key length). Given only the ciphertext, how can you decrypt the message? A step by step explanation would be greatly appreciated.


texts: How can prime factor of $q-1$ divide prime $q$?

texts:
In this paper - "A Subexponential Algorithm for the Discrete Logarithm Problem", author mentions (page 56),

For each $p_l^{e_l} | q$ proceed....

$p_l^{e_l}$  is one of the prime factors of $q-1$, and $q$ is a prime.
How can any number divide prime? Am I missing something here?
Edit1: $q$ is prime, so we can't get any non-trivial factor of $q$. Keeping this in mind, can anyone explain how to proceed with the steps mentioned in the paper. One thing to keep in mind is that $q$ has to be prime to be used in Diffie-Hellman system.


texts: How can I avoid side channel attacks to scalar multiplication of Ed25519?

texts:
I'm a beginner at working with Edwards Curves, and I'm trying to implement an Ed25519 signature. I have a question from a text.  Please see the illustration below (in Python).
At the part of scalar multiplication it simply uses the double-and-add method:
def point_mul(s, P):
    Q = (0, 1, 1, 0)  # Neutral element
    while s > 0:
        if s & 1:
            Q = point_add(Q, P)
        P = point_add(P, P)
        s >>= 1
    return Q

Is that safe enough?
Why doesn't it use a constant time method like x25519 for DH key exchange?
There is the Montgomery ladder as method of scalar multiplication of X25519 for DH key exchange to prevent side channel attack. How about Ed25519?
How can I protect against side channel attack when using scalar multiplication?
How can I modify the function?
I will implement with a hardware design after finishing the python implementation. Is there any method to prevent the attack?


texts: Explanation of Gallant-Lambert-Vanstone method / Endomorphism speedups

texts:
Can someone explain how the Gallant-Lambert-Vanstone method works (or which literature explains it)?

It is also unclear to me how the Frobenius endomorphism can be used in some cases for a speedup.

Also: how does it make sure that an attack remains infeasible (by using this method)?

(I am especially interested because of the sec256k1 curve which uses the method)


texts:
I probably have this doubt due to poor understanding of modular arithmetic, so an explanation would be greatly appreciated.

In any standard explanation of RSA, the following is present:

c = m^e mod n (where, c is the cipher text, m is the message, e the public key exponent, and n is the modulus)

And for decryption:

m = c^d mod n

To prove this, I've seen that the next step normally shown is :

m^(e.d) = m mod n

My question is, when c is raised to the private key exponent, why is the exponent not distributed over both m and mod n? I.E why is it not m^(e.d) mod n^(e.d)


texts: KRACK - Is all-zero key installed by the acces point?

texts:
I don't really understand (and I think it's not described in the official paper) how the encryption can work when the encryption key is set to 0 by a KRACK attack on a device using wpa_supplicant 2.4 or 2.5.

Does the access point have to install this all-zero key? how to force this installation?


texts: What are preimage resistance and collision resistance, and how can the lack thereof be exploited?

texts:
What is "preimage resistance", and how can the lack thereof be exploited?
How is this different from collision resistance, and are there any known preimage attacks that would be considered feasible?


texts: Is there a zero knowledge proof to show an encrypted blob is the key for a given public key?

texts: Let's say I have a private key x  with a corresponding public key y. If I encrypt x as E(x), is there a zero knowledge proof I can use to show that E(x) contains the private key for y?


texts: Decrypt simple CBC message with known IV using XOR encryption

texts:
I've been given a ciphertext message, encrypted using CBC. I know that the block size is 12 bytes and I know the plaintext value of the first block.

I also know that the encryption function is a simple XOR:

$$C_i = K \oplus (M_i \oplus C_{i-1})$$

where $C_0 = IV$.

Now I supposedly should be able to deduce the complete plain text message, but I'm lost. What sort of XOR'ing magic should I perform here to get hold of the plain text?


texts: Insecure MAC built on pseudorandom function

texts:
this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c.

For (a) and (b) it is clear that the Macs are insecure, but for (c) I am struggling to see why.

For me, when the attacker will present his pair $(m^*, \langle r^*,t^* \rangle)$, the MAC will sample uniformly its own $r$ (before applying the $\operatorname{Vrfyk}(.)$ algorithm), and will prepend $r$ to the computed $t$.

So no matter how the attacker will choose $m^*$ (even if the attacker chooses $m^*$ randomly), the MAC (assuming that it is a deterministic MAC using a canonical verification) will always sample a random $r$ from ${0,1}^n$, independently from the one $(r^*)$ that the attacker output to it, and the probability that $r=r^*$ will be negligible. So it is still secure MAC, the one presented in part (c).

Can someone correct me if I am wrong please?


texts: What does "Worst-case hardness" mean in lattice-based cryptography?

texts:
In the wiki page of Lattice-based Cryptography the "Worst-case hardness" is defined as below:

  Worst-case hardness of lattice problems means that breaking the cryptographic construction (even with some small non-negligible probability) is provably at least as hard as solving several lattice problems (approximately, within polynomial factors) in the worst case. In other words, breaking the cryptographic construction implies an efficient algorithm for solving any instance of some underlying lattice problem.

But what is the difference between "worst case hardness" in lattice-based cryptography and "average case hardness" in standard cryptography based on discrete logarithm, say ElGamal Encryption?

It's seems to be confusing. For instance, breaking into ElGamal Encryption also leads to breaking several other cryptographic constructions and solving well-known number theoretic hard problem:  computational Diffie-Hellman. However, that one does not considered a "worst case hardness".


texts: Zero Knowledge Proof AND Diffie Helmann?

texts:
From my research, I think what everything says is that the result of a zero knowledge proof (ZKP) is that the participants end up with a shared secret that can be used as a session key for a further symmetric encryption session between those two parties.  And then, all of the articles say that you follow this up by starting up something like a Diffie-Helmann (DH) session.

If I just got a secure key from the ZKP - why do I need DH?  Why don't I just expand the ZKP result and go from there?


texts:
I've been working through "Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality" 1 from earlier this year. My knowledge of OCB2 is pretty shallow though, and so I'm keen to study the scheme in depth before I continue.
From citations and searching around, it seems like OCB2 was introduced in a 2004 paper by Rogaway titled "Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC" 2.
There aren't any explicit mentions of OCB2 in this paper though. Section 10 is titled "The OCB1 Authenticated-Encryption Scheme" and includes a description of "OCB1 with an ideal tweakable blockcipher". The scheme described in that section matches what I have read about OCB2.
I suppose the scheme only started being called OCB2 after the publication of the paper? Is that correct? If not, where can I find a description of OCB2?


texts: When knowledge soundness implies soundness

texts:
In the work of Bellare–Goldreich that defines knowledge soundness BG92, the discussion of Section 4.5 specifically decouples knowledge soundness from soundness. That is, proving knowledge soundness for some verifier $V$ says nothing about the soundness of some pair $(P^*, V)$, for arbitrary (cheating) prover $P^*$.
However, in various works, notes, and related notions, knowledge soundness is taken to imply soundness.
In Lin03, arguments of knowledge are defined in Definition 9, and in the discussion below are said to directly imply soundness error at most the knowledge error.
In GI08, their particular notion of Witness-Extended Emulation, a more robust notion of knowledge, implies soundness.
Finally, in the notes of Bar07, the definition of knowledge soundness given is said to imply a soundness error at the most the knowledge error, just as in Lin03.
The one thing all the above examples have in common, which also differs from BG92, is that they restrict the class of provers $P^*$ against which knowledge soundness is proven for $V$ to at most expected polynomial time.
Intuitively, this seems like it should be the reason for knowledge soundness implying soundness, especially in light of the discussion in Lin03. Can anyone give a more a explicit answer about why Section 4.5 of BG92 is not relevant in these cases?


texts: Pollard's kangaroo attack on Elliptic Curve Groups

texts:
Let's say I've intercepted some bits of a Diffie-Hellman private key: $x = n \mod r$. I can get the remaining bits by doing a kangaroo search. This algorithm works over $\mathbb{F}_p$. Can it be adapted to the elliptic curve Diffie-Hellman problem?

In the ECDH problem over $\mathbb{E}(\mathbb{F}_p)$, we're trying to solve $y = x \cdot G$, where $G$ is a base point for the group. With the private key that I have so far, I have the following transformation:

$x = n \mod r \rightarrow x = n + m \cdot r$

$y = (n + m \cdot r) \cdot G = n \cdot G \oplus m \cdot r \cdot G$

So I want to solve $y' = m \cdot G'$ for $m$, where $y' \equiv y \ominus n\cdot G$ and $G' = r\cdot G$, and $\ominus$ is subtraction of points on the curve.

Basically, is the idea to replace exponentiation in the DH kangaroo algorithm with scalar multiplication, and multiplication in the DH kangaroo algorithm with group addition?

$y_{i+1} = y_i G^{f(y_i)}$ in the DH problem, vs.

$y_{i+1} = y_i \oplus (f(y_i) \cdot G)$ in ECDH?

There are faster ways to do scalar multiplication on elliptic curve points, such as the Montgomery ladder, but that only gives you the x-coordinate of the scaled point.

Do I have the right idea about translating this algorithm to the ECDH? Let's assume that I know about Pollard's rho, Shanks' baby-step-giant-step, etc., but that I really want to get this kangaroo working (er, hopping).


texts: Variant of the Decisional Bilinear Diffie Hellman problem

texts:
I am working on a cryptographic scheme and I need to rely on the following problem, which I have nicknamed the "Hybrid Decisional Bilinear Diffie Hellman (hDBDH)" problem:

  Let $e: \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$ be an efficient bilinear pairing. Given the tuple $(g,g^x,e(g,g)^y,Q)$ as input, the problem is to decide whether $Q = e(g,g)^{xy}$

First, has this problem already been defined? Now, I want to prove that this problem is equivalent to the DBDH problem. I have the feeling that they are equivalent, but so far I only have that $DBDH \leq hDBDH$:

  Proof: From a hDBDH solver, we can construct a DBDH solver in the following way:

  Input: DBDH tuple = $(g, g^a, g^b, g^c, Q)$

  Output: Return $hDBDH_{\mathsf{solver}}(g,g^a,e(g^b,g^c),Q)$

Now I want to prove the other direction. Any ideas of how a DBDH oracle could be used to solve the hDBDH problem? Any ideas of why it is not possible?


texts: Elliptic curves over extensions of 64-bit fields

texts:
Are there any standard (or at least well-know) elliptic curves over $F_{p^4}$ where $p$ is a ~64-bit prime? I know Microsoft has FourQ curve which works over $F_{p^2}$ where $p$ is a 127-bit prime, but I haven't come across any curve that works over extensions of ~64-bit fields.

If there are no standard/well-know curves that fit this, are there any fundamental reasons for why elliptic curves over $F_{p^4}$ would not be a good idea?


texts: How is message length involved in public/private-key encryption?

texts:
I've just read this question regarding why to sign only the hash of a message. I kind of understood the answer, but the question arisen is now:

Why can I encrypt any text messages with the same method while it is needed to split up the message in order to sign it?

I mean, signing is taking the private key and encrypting e.g. message A and on the other side taking the encrypted message and using the public key to decrypt it. What is the difference that makes the other way around (public key for encryption, private key for decryption) (more) secure?


texts: Is it safe to derive two different keys with the same password and key derivation function using two different salts?

texts:
I would like to know if the following process would harm the security of a fictional system if the persisted data would be stolen: in this system a user has a single password. The password will be used in order to derive two different keys using the same key derivation function (PBKDF2/bcrypt/scrypt) with the same parameters but using different salts. One of the keys will be persisted on the system, the other will not. Both salts will be persisted, too.

Would the persisted key, besides allowing the theoretical brute forcing using the corresponding salt in order to retrieve the password, allow the attacker more information regarding the second key? Does it depend on the actual KDF?


texts: Why do public keys need to be validated?

texts:
For some curves it's necessary to validate the public-key of the other side before running an elliptic-curve Diffie-Hellman key-exchange. Apparently if you don't validate the public key, small subgroup attacks can leak your private key.

I have a few questions related to this issue:

Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?
Which validations need to be performed? Just check if the order of the point is large enough?
Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?


texts: Registration and log in through public key cryptography?

texts:
I read about zero knowledge proofs.

Let's say you want to create an account at a website. You choose a password $p$ and from $p$ you derive deterministically a public & private key pair $(e,d)$ and send $e$ to the server. Every time you want to log in, you and the server play a game: The server sends you an encrypted message containing a random number, and you decrypt it and send it back; this proves you have knowledge of the private key and the password without revealing either. Is such a scheme used?


texts: What is the fastest integer factorization to break RSA?

texts:
I read on Wikipedia, the fastest Algorithm for breaking RSA is GNFS.

And in one IEEE paper (MVFactor: A method to decrease processing time for factorization algorithm), I read the fastest algorithms are TDM, FFM and VFactor.

Which of these is actually right?


texts: Can the salting function complexity improve the hash robustness?

texts:
I'm quite novice in security, and all examples I saw seem to salt the password by concatenating it, or by applying a simple binary OR or XOR. So the hash is based on "salt + password", "salt | password", etc.

If I'm right, a hacker should know how the password has been salted in order to retrieve a user password. So, can the complexity of the salting method improve the overall security?


texts: formulas for adding points on curve25519

texts:
Curve25519 is a Montgomery curve. https://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html#diffadd-dadd-1987-m-3 gives a set of formulas for adding two points (well, more specifically, the X coordinate in XZ form):

  A = X2+Z2
  B = X2-Z2
  C = X3+Z3
  D = X3-Z3
  DA = D*A
  CB = C*B
  X5 = Z1*(DA+CB)2
  Z5 = X1*(DA-CB)2

This series of formulas gives 3x XZ coordinates - not 2x. (X2, Z2), (X3, Z3) and (Z1, X1). If I'm trying to add two points I'd expect two sets of XZ coordinates - not 3x.

Are the formulas wrong or am I missing something?


texts: Making ECDSA public keys one bit shorter

texts:
In compressed form, ECDSA public keys are one bit larger than the curve size. There are some situations where this extra bit is extremely inelegant. So I had the following idea as a way to remove it.

For a public key, the extra bit is always zero and so does not need to be sent.
If a private key produces an extra bit of one in the public key, it is not used. (In SECP256K1, some private keys have to be folded anyway, so this would just be folding more keys.) One suitable folding method would be to generate a new random private key. Another, probably slightly less optimum, would be to keep incrementing the private key until a valid one was found.

I'm interested in the security consequences of doing this. The following are my educated guesses, in order of my confidence in them:

This is definitely no worse than picking an equally secure curve that is one or two bits smaller. So it can't be less secure than, say, SECP224K1 unless SECP256K1 is broken or SECP224K1 is somehow unusually strong.
This is actually stronger than that because although only half the private keys are valid, an attacker probably can't really take advantage of that fact.
In fact, it doesn't weaken the algorithm at all. We could probably even force the first 4 bytes of the public key to be zero if we wanted and the only real cost would be that it would be a lot harder to find a valid private key. The private key search space is actually no smaller, only the chance of colliding keys is higher, which is still effectively zero. Only reducing the private key space in ways an attacker can take advantage of make the algorithm less secure.

Am I correct?


texts: Are there any natural ways to transform ElGamal encryption system or ElGamal signature scheme into an authentication protocol?


texts: What is the most paranoid way to exchange messages?

texts:
I'm looking for a way for Alice to send a message or a file to Bob in the most paranoid way possible (over the internet).

It can be asymmetric or symmetric. But According to some articles, AES 128bit, RSA, ECC are all broken or will be soon (with the new NSA Utah center).

I found PHPECC library on GitHub: https://github.com/mdanter/phpecc but I don't know how to generate private keys and change key length.

RSA is slow to get a decent security... AKA 2048-bit or more.

AES-256bit is fast and secure with a strong password... but I cannot figure how to communicate the password in the most paranoid way. (Again, please, not on a piece of paper :))

I've made a couple of schemas on a sheet, but I'm sure there's a better way than what I've imagine.

Any help or explanation, or good methods how to do that will be greatly appreciate.

EDIT:

OpenSSL Vulnerability: http://www.theregister.co.uk/2010/03/04/severe_openssl_vulnerability/

AES 128-bit: http://threatpost.ca/en_us/blogs/rsa-2010-experts-expect-several-ciphers-be-cracked-soon-030210

NSA is promoting ECC over RSA. And ECC 112-bit is broken:
http://www.nsa.gov/business/programs/elliptic_curve.shtml

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography


texts: Computational benefits of using exponent as a power of 2 in Ring-LWE

texts:
In most of the RLWE based cryptosystems, the parameter $n$, which defines the cyclotomic polynomial $\Phi_{n}(X)$, is chosen to be a power of $2$.
Apart from other benefits such as ease of writing proofs and simplicity, are there any significant computational benefits?


texts: Apple CryptoKit - Understanding its portability

texts:
I've been playing with Apple's CryptoKit (their effort to make their old CommonCrypto lib more modern and easy to use via Swift, their programming language).

I'm interested to see how portable it is...

They use boxes, similar to libsodium.

Interestingly they only support AES-GCM and ChaChaPoly for authSym, and a handful of curves for Asym (P-256 & Curve25519 being most notable).

Anyway, I'm just trying to decrypt some test data manually (using OpenSSL or whatever) using the raw outputs I've extracted from the debug code I wrote, and whilst I can encrypt and decrypt in Swift I'd love to test this elsewhere to check portability.

This is AES-GCM-256,

Key Base64: nUSfBvhz2HSSo575uCOK3ewTibD7jXsp6f2aPfP3dTo=

Nonce:m2A7P8c5r7wmczXD

Ciphertext:uEU5otv81AMjG9wCxg==

Tag:w1lj7fumWRQ7hdJCXwkqCw==

Can anyone help me use OpenSSL on command line to decrypt?

I've been trying OpenSSL enc aes-gcm-256 -a -d without getting it working (-a for base64, -d for decrypt)...


texts: Where can I find names for cryptographic notation I don't recognize?

texts: I'm new to this space and find myself stumbling over come cryptographic/mathematical notation. Search engines are not very helpful when copying and pasting Greek letters. Is there any reference that can at least give me names of what I am looking for?


texts:
I am unable to understand why - using a counter comparison based ring oscillator PUF - the output bit is either 0 or 1.

Since the output is one bit I don't see how multi bit responses are obtained. Using this information how can I calculate intra- and inter-Hamming distance? Can you provide some provide example to explain it?

Using ring oscillator based PUF proposed by Devadas and Suh it compares counter values and then produces 1 bit of output. So from this one bit of output, how is it possible to get a multiple bit response to calculate intra- or inner-Hamming distance?

.

If I apply input of 1001010 it is input to two sets of ring oscillator each having 128 ring oscillator out of two set one from each a ring oscillator is  selected and feed to counter and comparator produces output 0 or 1.

So a single bit response is obtained But in the paper of Devadas and Suh : https://people.csail.mit.edu/devadas/pubs/puf-dac07.pdf in figure 4 for challenge  1001010 the response is 010101. How is this possible?


texts: TLS: How is the shared secret (via Diffie-Hellman) used in the symmetric crypto function?

texts:
So let's say we use a cipher suite with DH key exchange and AES symmetric encryption. Alice and Bob both end up with the same shared secret key $k$.

How is this value k used in e.g. AES? Will it be hashed before use, or is there a PBKDF involved? And what do we do about small $k$ (e.g. $10, …$)


texts: What can I do if I get private key of signing algorithm in Digital signiture

texts: I am confused in digital signature. what is use of encryption with private key and decryption with public key. Using public key we can decrypt the signature then what is use of private key privacy. Explain in detail.


texts: Hash function on byte arrays, with independent order

texts:
I would like to have a hash function $H(a_1,...,a_n)$ with the following properties:

$a_1 ... a_n$ are byte arrays with same size (typically 32 or 64 bytes).
It should also allow "easy" update or deletion of a single element, i.e :

$H(a_1,...,a_{n+1}) = f(H(a_1,...,a_n), a_{n+1})$
$H(a_1,...,a_{i-1},a_{i+1},...,a_n) = g(H(a_1,...,a_{n}), a_i)$

The order of the $a_1 ... a_n$ terms for $H$ function does not matter.

I found a similar question, but I don't think it can easily handle the single item deletion requirement: Is there such thing as an order independent, updatable hash?

Thanks in advance!


texts: Why use an RSA public key exponent of form $2^n+1$ instead of $2^n-1$?

texts:
The short exponents in RSA which are only a few bits in length,i.e. $e=3,\ 17$ and $2^{16} +1$

Why we are using exponents of the form ${}2^n+1$ not $2^n-1$?


texts: Weil pairing implementation - low level programming language

texts:
I'm just started to studying elliptic curve cryptosystems. My one month-goal is to write a simple signature system based on the Weil-pairing. Some parts of it can be written without deeper understanding, so I decided to start it with the easier parts right now.

I've searched for some ideas on internet, but all I've found was very high level solutions (f.e: SAGE).

Can this system be written in a lower-level language like C? I mean: of course, everything can be done in C, but does it contain parts that are too hard to code it?

For example: finding the derivative of a function is really hard in C.

Thanks for the answers!


texts: Proof that MAC and hash composition is insecure

texts:
Let $F$ be a secure PRF and $H$ a universal hash function.

How can I exhibit a pair $(F,H)$ whose composition $$S'((k_1, k_2), m) = F(k_2, H(k_1,m))$$

is an insecure MAC (or an insecure PRF, since a MAC can be defined as a PRF) ?

I guess that, in order to find a pair $(F,H)$, the trick would be creating some $H$ whose image space is short enough so to easily find a collision, but I'm not good at finding an example of such functions, the books I read always try to abstract these functions.


texts: Any side effects of switching from Rijndael to AES in a .net application?

texts:
Our company would like to update our .Net apps so that they can run on Windows machines that require FIPS compliance. Currently we are using the System.Security.Cryptography.Rijndael class. I changed our encryption methods to use Cryptography.Aes instead and our apps are able to run on machines with FIPS compliance enabled and appear to function exactly the same.

That seems too easy. So my question is: are there any side effects to switching to AES that aren't readily apparent? Or does the encryption method not matter as long as the inputs and outputs are the same?


texts:
ECB is considered to be insecure when used for confidentiality because identical plaintext result with identical ciphertext. But what if we use ECB for authentication?

Assume A wants to transmit an authenticated message X to B. A and B have a shared key. What if A encrypts the plaintext X using AES-ECB and outputs Y as the ciphertext and appends it next to the plaintext X as a MAC? Would that be secure?

Confidentiality is not of importance here. We only need to authenticate the data.


texts: I think I'm trying to find the C in an RSA cipher to find the key for an aes_128_ecb cipher, can anyone tell me if I'm on the right track?

texts:
And if I am on the right track, how do I reach the solution from here?

I'm doing a CS game and I've hit a wall (I'm a rank beginner when it comes to encryption) on the encryption portion. I've been given the encrypted output and what I think (from my research) is an encoded version of the key using this:

For me, C is what I'm looking for, d = 7, N = 98286183916580532129117891164396375520832348985166654489180704043300879122347 and P = 89511674269883781051088511817946305647658886680759682801944853433540569894936.

p and q for N are 294156383975755063828794349953398256143 and 334129018681034197306379539716603659429

C was created randomly and is known to be 16 bytes. P is known because it was the first 32 bytes of the encrypted file (that I ripped out using a hex editor and turned into base 10) and d and N were both hardcoded.

I tried reversing it manually (using modular arithmetic, since a = b mod n then b = a mod n so C = root7(PmodN) ) but I got a 37 byte number that I know must be incorrect. Can someone please tell me where I'm going wrong?

I can post the source if it's necessary.


texts: How much time will it take to crack PBKDF2 while using a 9 character password? I'm not specifying any specific system or platform. If a brute force attack is made using the best ever super computer around how much time will it take to crack it?


texts: What is Frobenius map of an elliptic curve?

texts: I was reading about elliptic curves from this PDF. Page 44 defines Frobenius map. It defines the frobenius map as $f(x,y) = (x^p, y^p) \bmod p$. Isn't it just an identity map? What's the use of this map in elliptic curves?


texts:
I was trying to implement zero knowledge protocol for authentication based on the paper "A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory".

In that, the first step is…

  each security device with identity $I$ receives an authentication value $B$ (The inverse of $A$ modulo $n$) computed by some authority from $A=J^{1/\mu} mod\ n$, where $J$ is the shadowed identity $I$

Also, they have defined “shadow” as…

  Shadow: One first completes a short message (half the length of a public modulus $n$) with a similar sized redundancy, named shadow, then extracts the $\mu^{th}$ root of this element in the chosen ring based on the composite integer $n$.

From my point of view (being a programmer), I do not understand what this “shadow” is and how to calculate it.

Also there is a sentence…

  then extracts the $\mu^{th}$ root of this element in the chosen ring based on the composite integer $n$

How I set the value of $\mu$? Can I take any arbitrary value? What is the significance of that value?

  Also there is a step $t=r.B^d\ mod\ n$. This means $(r.B^d)\ mod\ n$
  or $r.(B^d\ mod\ n)$?


texts: Sharing salt for deterministic symmetric key derivation

texts:
I have a requirement to generate and share unique symmetric keys for a large numbers of small data objects.

In many cases the storage and retrieval of the key for each object will be a significant overhead, and often larger than the individual data objects they secure, so am looking for a strategy that mitigates this.

I am wondering if I could securely distribute a single master key for sets of these data objects, and then use a unique salt to derive a key for each data object.  The salt would then be shared to allow a recipient to derive the same key for that object.

Every time the data changes for a specific object I would generate a new salt, derive a new key from the master key, re-encrypt the data and share the new salt.  Sharing a new (say 96 bit) salt for each object would be significantly smaller than sharing an entirely new key.

(I am making the assumption it would be more efficient for the recipient to receive a new salt and derive the key, rather than receiving and importing a key for each object)

Update to add more info:

The design is such that these data objects might run into the the
many 10s of millions, at a guess mostly < 200-300 bytes in size.
The data objects are unrelated, and will be accessed randomly by any number of
recipients.  The set of data objects any one recipient may access is
unknown at creation time.
Access times to the plaintext of these data objects is significant, as is their over-wire cost
The server verifies access tokens presented for the data object, but
beyond a signature has no knowledge of ownership or the content of
them.
A single recipient may have access to 100s or 1000s of these objects,
such that storing & retrieving unique keys for each is undesirable
Access to one data object shouldn't convey access to another


texts: Why must an elliptic curve group for ECC have prime order?

texts: What is the deeper reason, a group must have prime order for usage in cryptography?


texts: Block cipher unconditional security under ciphertext only attacks

texts: Does there exist a block cipher which provides security against ciphertext only attacks, which has an unconditional security proof guaranteeing this is true?  I know the existence of a provably secure block cipher with unconditional proof is not yet known, but I am unsure if there exists a block cipher that is provably secure against just ciphertext only attacks.


texts: Is the scheme $(r, Mac_k(r) \oplus m)$ CPA-secure?

texts:
I honestly admit this question is taken from a h.w assignment:

  Prove or refute: the following encryption scheme is CPA-secure: Let $(\text{Gen},  \text{Mac}, \text{Vrfy})$ be a secure MAC with tags of length $n$. Encrypt a message $m \in (0,1)^n$ by choosing a random $r \in (0, 1)^n$ and outputting $(r, \text{Mac}_k(r) \oplus m)$.

As I just have started with this course, please point out if my approach or my usage of technical terms are incorrect or imprecise. I am following the book named "Introduction to modern crypthography."

My first approach was to refute the claim. I thought about giving an example for a MAC that is secure but yields a non-secure scheme. For instance, consider the MAC which appends a zero at the end. As far as I can tell,  a PRF $f$ can be used as a MAC, so I could define something like $\text{Mac}(x) = f(x) ||0$ or, even, use some other MAC instead of $f$. It's easy to see that the scheme will not be CPA-secure as an adversary's decision can base solely on the last bit of the message.
In contrast to my first approach, I would actually like to prove it. My intuition tells me, given a random $r$, $\text{Mac}_k(r)$ should be also random. Thus, I get a random string XOR'ed with $m$ (which actually seems like an OTP), which should be secure.
The problem is that I don't know how to complete my proof by reduction. If I build an attacker $A'$ how it should interact with the other attacker $A$? I would start by assuming the scheme is NOT CPA-secure and would come to a contradiction by giving a MAC which yields a scheme which is not CPA secure---but I am very confused on how to do it.

It would be really nice if I could get some clues or related examples on how to formalize my line of thinking.


texts: Confusion on Private Information Retrieval by Keywords

texts:
PIR protocols retrieve an item from the database without the server knowing which item it is. But classic CPIR(Computational PIR) or IT-PIR (Information Theoretic PIR) protocols requires the user to know the location address of the object to be retrieved.

Major work on retrieving by Keywords is done here and subsequently here extended for SQL databases. An excerpt for more context.

  For B+ tree indices, however, the client uses PIR to traverse the
  tree. Each block can hold some number m of keys, and at a block level,
  the B+ tree can be considered an m-ary tree. The client has already
  been sent the root block of the tree, which contains the top m keys.
  Using this information, the client can perform a single PIR block
  query to fetch one of the m blocks so referenced. It repeats this
  process until it reaches the leaves of the tree, at which point it
  fetches the required data with further PIR queries. The actual number
  of PIR queries depends on the height of the (balanced) tree, and the
  number of tuples in the result set. Traversals of B+ tree indices with
  our approach are oblivious in that they leak no information about
  nodes’ access pattern; we realize retrieval of a node’s data as a PIR
  operation over the data set of all nodes in the tree.

A more general approach is like below

  The main idea in all of our subsequent PERKY constructions is the
  following: the databases insert $s_1, s_2 .. s_n$ into a data
  structure which supports search operations on strings. The user
  conducts an oblivious walk on the data structure until either the word
  $w$ is found, or User is assured of the fact that $w$ is not one of
  $s_1, s_2 .. s_n$. Typically, a successful search yields an address
  which contains data pertaining to the keyword.
  A typical search in the data structure involves a sequence of operations, where each operation consists of fetching the contents of a word from memory, performing
  a  "local" computation, which depends on the keyword and the fetched
  contents, and either determining a new address based on the
  computation, or terminating the search (successfully or
  unsuccessfully). This sequence of operations can be viewed as a $walk$
  on the data structure. We now describe a general outline of
  transforming this walk into an oblivious walk on the data structure,
  namely a walk where each server gets no information on the walk (and,
  therefore, on the desired keyword itself). For the sake of simplicity,
  we assume that the data structure has a fixed $root$, a word with
  known address that is always accessed at the first operation
  (regardless of the sought keyword).

But either i don't understand it or it seems to be weak. If a $walk$ ends after two iterations then an adversary is pretty sure that the retrieved element is in first two iterations right ? Or how does PIR by keywords in general work? any simpler explanations ?


texts:
This is a multi-layer problem, and I want to take you through the whole thing rather than just asking about IVs. Bear with me. Also, all code below is in Common Lisp because that's what I'm using, but if there are any complaints, I'll edit to put up pseudocode.

I'm trying to put together a procedure which will produce hard-to-guess session tokens for use in a server implementation. What I've got so far is

(ql:quickload (list :ironclad :cl-base64))
(setf *random-state* (make-random-state t))

(defmethod sha256 ((message integer))
  (ironclad:digest-sequence
   :sha256 (ironclad:integer-to-octets message)))

(let ((cipher (ironclad:make-cipher :aes :mode :ecb :key (sha256 (random (expt 2 1024)))))
      (counter (random (expt 2 512))))
  (defun new-session-token ()
    (let ((raw (ironclad:integer-to-octets (incf counter))))
      (ironclad:encrypt-in-place cipher raw)
      (cl-base64:usb8-array-to-base64-string raw :uri t))))

A side question here: what vulnerabilities does this approach have over using AES in counter mode?

The way to use this in counter-mode would be to change the line that defines cipherto :

...
(let ((cipher (ironclad:make-cipher
           :aes :key (sha256 (random (expt 2 1024)))
           :mode :ctr :initialization-vector [16-element vector goes here])
...

My questions are as follows:

What properties does that IV need? The only one I've seen mentioned is uniqueness, which implies that it doesn't have to be secret.
Do I need to generate a new one each time I generate a session token?
What's a good way of generating one?

EDIT:

As per comment by Stephen Touset, Ironclad supports CSPRNG out of the box (more specifically, it supports Fortuna. For my purposes, the above functions can be replaced with

(let ((prng (ironclad:make-prng :fortuna)))
  (defun new-session-token ()
    (cl-base64:usb8-array-to-base64-string
     (ironclad:random-data 32 prng) :uri t)))

ironclad:make-prng seems inconsistent in runtime; I've timed between 8 and 70 seconds.


texts:
In Fiat-Shamir protocol, the final calculation is

$$y^2=x\,v^c$$

Where $c$ is the random $\{1,0\}$, $x$ is the witness and $v$ is the public key $s^2 \bmod n$.

My questions are:

What stops the attacker from reading $c$, which is never encrypted,
   $v$ which is public and then calculate $y^2$ correctly?
How does this improve entity authentication?


texts: Why "pairings on elliptic curve" are used?

texts:
I'm just curious why do we use pairings on elliptic curve cryptography.
There is a lot of information about how to use it, but I cannot find information about why to use it.
Can somebody help?


texts: Symmetric mutual authentication with client using a derived secret

texts:
I'm attempting to find a client/server authentication protocol that allows the client and server to authenticate each other when the client doesn't know the server secret but does have a sensitive key derived from the secret.

I would like to use asymmetric certs, but the server in this case is extremely limited in CPU and memory resources, on the order of 16MHz and 32K Ram; but it does have hardware AES support. Speed of the process is critical to the user-experience, but security is paramount.

I was thinking through it and I'd like something like this (The most secure form of each function is implicit):

ClientID (CID): Unique client identifier that ties the token to the client.

Client Token (CT): HMAC(Secret, CID)

Secret (S): A secret that the server knows. The server (or a third party that also knows the key) creates tokens through an offline commissioning process.

Client -> Server
CID, CNonce

Server -> Client (Server derives expected CT with secret and CID)
SNonce, HMAC(CT, CNonce)

Client -> Server
HMAC(CT, SNonce)

This seems to give me a few properties that I need:

The client can verify that the server knows the secret because it is able to HMAC CNonce with a derived CT.
The server can verify that the client has the token because it can HMAC the SNonce with the CT.
Replay attacks are mitigated by the nonces.
MITM attacks mitigated because the token is never transmitted.


texts: What is the difference between the keylength and the length of a password for AES-256?


texts: How can Cipher Block Chaining (CBC) in SSL be attacked?

texts:
I am trying to understand how CBC-mode in SSL/TLS can be attacked.

I have been looking around online but all examples and explanations are very hard to understand and follow. Can you give a simple explanation for how such attacks happen?


texts: Why is "mod(n)" so central to most aspects of cryptography?

texts:
When I first started learning cryptography, I had my first a-ha moment when I fully appreciated the value of a One Time Pad and XOR and all the functions that attempt to emulate that OTP's randomness (PRP/PRF).

Now that I'm learning about the math behind various lemmas, I see a recurring theme regarding "take the modulo of a number, and then do f()".  That is a reoccurring theme that I don't fully appreciate, or understand.

So why is mod(n) used so frequently in cryptography?  What is consistent, special or useful about mod(n) that makes it so consistently used by cryptographers such as XOR is?


texts: Where is defined the fact of having a "learning" and "challenge" phase in cryptography proofs?

texts:
I've read Bellare and Rogaway 2004 and Shoup 2004 about game-based cryptography proofs, but I lack precisions about how should be built the "learning" and "challenge" phases, since my games will probably have this structure.

And what are they suppose to provide anyway ? Security against Adaptive adversaries ? The games I have read are like:

learning phase: do whatever you're allowed to do
challenge phase: submit two challenge sets, read what the oracle send you back and guess which set has been chosen

Yet adaptive adversary should mean (citing wikipedia) ciphertexts may be chosen adaptively before and after a challenge ciphertext is given to the attacker

thanks for explanations and/or links


texts: Rogue CA Certificate MD5 Collision Control

texts:
Papers from Marc Stevens et al show that X509 certificates that rely on MD5 signatures can break the assumed security model, that is, it allows for a forged certificate to have the same signature as a trusted cert, see https://marc-stevens.nl/research for these papers.  Both methods require the "to be signed" portion of the certificate to be known in order for the collision search to begin. Both require some "control" over the CA, whether it is by setting a fake CA or correctly predicting the validity and serial fields.

My question is why is this necessary? I understand that I need to know the to be signed parts, but why can't I just get this information from an already generated cert? I must be missing something simple about how these certs are constructed.


texts:
I’ve been tinkering with SHA-3 for a little bit, and I have some questions regarding the applicability of cache timing attacks on this particular hash function.  The two sub functions that I believe are susceptible to this particular attack are THETA and CHI. I think I can prove that THETA does not run in constant time, depending on the particular method with which the algorithm is implemented, and I believe CHI does not run in constant time either. To prove that statement with CHI would require the addition of break statements in some implementations of that function. Something that I have yet to complete.

Now assuming that the attacker only has access to a static SHA-3 hash output, I doubt that any information can be gained about the input. However assuming the attacker is able to monitor the execution time of the hash function things get more interesting. Although I'm not sure how prevalent this second scenario is in real life. All that would be gained is the total execution time of all 24 rounds of THETA, but would it be possible from this value to determine the execution time of individual rounds of THETA? Or then be able to approximate inputs based on execution time?

Does anyone know of any references/articles related to SHA-3 and cache timing attacks?


texts: Mathematics behind end-to-end encryption

texts:
I am interested in end to end encryption, recently I read some articles on its principles but I can't find anything on the maths behind the encrypting and decrypting functions that relates private and public keys. I remember to have read that they are related with prime numbers and elleptic functions but I haven't find anything else.

Can anyone tell me something else about it or suggest me an article/book on it?


texts: Attacks on WinRAR volumes reusing same password?

texts:
I have quite a few WinRAR volumes that are all encrypted with the same password. The password is long and unbruteforceable, but I recently read that WinRAR uses PBDKF2 as its key-derivation function instead of generating a new volume key every time like TrueCrypt, which means that in essence all of these volumes have the same 256-bit key.

Does that mean that if attackers got ahold of these volumes, they can use techniques similar to crib-dragging to extract the master password? Also, are these kind of attacks practical (i.e. have there been published success stories of such attacks)? I tried searching on Google but found nothing close to what I wanted.


texts: Why do MD5 and SHA-3 use different padding schemes?

texts:
What is the rationale for the difference between MD5 and SHA-3 padding schemes?

MD5 appends 10* and then the 64-bit message length in bits.
SHA-3 appends 10*1.

Why do they use different padding schemes?  MD5 is based on the Merkle-Damgard construction, while SHA-3 is based on the sponge construction—is this relevant?


texts: How to calculate if probability is negligible or not

texts: If i have probability $Q = 2C(A\times B)$ where $A$ and $B$ are unknown probabilities and $C$ is a non-negligible probability, what can i speculate about probability $Q$ and how can i calculate bounds on probabilities $A$ and $B$ in order to make this value non-negligible?


texts: Removing "security by obscurity" from port knocking

texts:
Every article about port knocking, for instance  https://wiki.archlinux.org/index.php/Port_Knocking , declares this method as security by obscurity.  Is the following enough to remove that title;

a scheme where a 2048 bit shared key is generated. Every 2 bytes of the key are chunked off to make a list of 128 port numbers (2048/8/2). These port numbers in order are then configured as the port knocking sequence.
the MAC address of the sender is also factored in (maybe as the first 6 bytes of the key)

Does this fix the "Security by obscurity" aspect of port knocking?

I understand that this is a sniffable method. Thanks for your feedback!


texts: One-way function and uninvertible function

texts:
How can I prove the following:

  If $f$ is a one-way function, then it is an uninvertible function?


texts: it the following example for page 56 of the book http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf I could not understand how the author found the Weil pairing of two points p and Q. I attached the picture of the example. Can you help me to this? Thanks.


texts:
My goal is to create a random $k$ bit string. My question can be divided in two parts.

If a $n$ bit string $s$ is computationally indistinguishable from a random $n$ bit string, can we say that the string $s$ has $n$ bit min entropy?
But for some reason I can't use the string $s$ directly, I need to convert it to another $n$ bit string $s'$. During conversion something bad happens. The probability of each bit being $0$ or $1$ is not $1/2$ anymore. It is $1/2+e$. Hence the min entropy of the bit string $n$ changes. Let the min-entropy of $s'$ be $l>k$. As hash functions are good randomness extractor, if I apply a hash function $H$ on the string $s'$ that produces $k$ bits, can I say the output of the hash function is a $k$ bit random string?

Thank you for your help.


texts: Why does the DBDH simulator have half the advantage of an adversary?

texts:
Literature that includes the DBDH assumption such as this paper or this paper has a formal security proof that states:

  Suppose an adversary with non-negligible advantage $\varepsilon = Adv$. A simulator is constructed that can distinguish a DBDH element from a random element with advantage $\frac{\varepsilon}{2}$.

Why is the advantage of the simulator ($\frac{\varepsilon}{2}$) half of that the adversary ($\varepsilon$)?


texts: Difference between MPC and outsourced computation

texts:
I am reading an introductory paper on multi-party computation (MPC), and it makes a distinction between outsourced computation and MPC.

  In an outsourced computation, one party owns the data and wants to be
  able to obtain the result of computation on that data. The second
  party receives and stores the data in an encrypted form, performs
  computation on the encrypted data, and provides the encrypted results
  to the data owner, without learning anything about the input data,
  intermediate values, or final result. The data owner can then decrypt
  the returned results to obtain the output.

After reading this, I  found outsourced computation and its difference to MPC is not quite clear. In MPC, parties can send their encrypted data to a trusted third-party to compute a result that then gets delivered back to them. This seems like what was described above, no?

My thoughts to justify the difference include:

Perhaps outsourced computation only involves two parties, the data provider and the data processor
Perhaps outsourced computation does not require the individual to send encrypted data to the second party

In summary, what is the difference between MPC and outsourced computation?


texts: Selective and existential unforgability of signature schemes

texts:
I understand that one can define EUF-CMA of a signature scheme is terms of a game where the adversary is allowed to query signatures on messages of his choosing, and at the end of the game he must output a pair (m, s) such that s is a valid signature of m, and m has not been queried before. My questions are the following:

How does one select selective unforgability under chosen message attack in terms of a game?
Are there examples of signatures which are SUF-CMA, but not EUF-CMA?