texts: Pairing — Finding points which are depicted in different cyclic subgroups?

texts:
I am reading the book Pairing for beginners (PDF) to understand pairing.

In the following example for page 52 of the book, I could not understand how the author depict the 4 cyclic subgroups and how he found different points in different cyclic subgroups. I attached the picture of the example.

Can you help me understand how the author found the points which are depicted in different cyclic subgroups like $(8, i), (8, 10i), …$?


texts: Selecting bijective functions for permutations

texts:
How would one go about selecting an appropriate bijective function for introducing permutations into a cipher or hash?

For example, $f(x) = x+1 \space mod \space n$ is a bijective function, but isn't particularly good as a permutation, in that the outputs do not vary sufficiently when an input bit is changed.

The same applies to $f(X_i) = X_{\sigma(i)}$, where $\sigma(i) \equiv i+1\space mod\space |X|$, i.e. a circular shift.

If I understand it correctly, modular exponentiation can be bijective if you select appropriate parameters, but it's rather slow.


texts: Encryption algorithms and the "One-Time pad"

texts:
I am not well versed in the field but I believe I know the basics.

All encryption algorithms that I know of utilize direct data manipulation to encrypt a message (string of bits) such as shifting, cycling, etc. in specific patterns utilizing the encryption key.

Is there any algorithm that instead of touching the data-to-be-encrypted in any way instead generates a secure one time pad using a reasonably short key?

I suppose technically in this scenario you would call the key a seed for a pseudo-random number generator.

So my question is this, does such a generator exist in a secure form and with an algorithm that can turn a phrase into a key or just generate such a key.

If there is such a generator I suppose you will point out the weakness of a one time pad on changing/multiple data, but suppose it isn't a concern due to pad use markers or simply because there is no other data or changes.


texts: Largest number that could be factored in milli seconds

texts: Considering a home pc/laptop as machine used (Say typical 2.4 GHz, 16GB RAM, 4 core processor) for running any factorization algorithm. What would be the largest number that could be factored into its prime factors in milli seconds ? rather how many digits such number might have ?


texts: Is there a counter mode of encryption where the key is being changed for every block of data?

texts: I thought like encrypting an IV concatenated with a CTR but instead of XOR-ing this output with the plaintext this output should be used as a temporary key for another encryption block that actually converts the plain- to ciphertext. In other words in a regular CTR mode of operation the XOR would be replaced by a full encryption algorithm and the OTP would be its key.


texts: Where does the meaning of reduction to a hard problem lie?

texts:
Given a protocol, if we can reduce breaking the protocol to a hard problem, such as DLP or CDH, we can say that this protocol is secure.
Theoretically speaking, reduction is a good method to prove the security of a protocol. As to key-exchange protocols, if the reduction method uses the adversary as a subroutine, the simulator will construct an algorithm. If the adversary can break the protocol under a certain model, then the simulator can solve a hard problem, say CDH.
However, in practice, can the simulator's algorithm be realised with a computer program? Moreover, does it work?


texts: El Gamal Signatures, Need help explanining a step, Where does the "775" come from? Image included

texts:
I understand all of the previous steps, but I don't understand what is happening to "S2" in that the number "775" showed up.

Where does the 775 come from? I can't seem to get it, and I've tried modding it, but received the wrong answer.

The answer to this is to add the modulo to the a when a is negative. As such, this worked out fine after I added the modulo to the negative number.

Solved!


texts: Chaum undeniable signature - justification for probability of misleading the verifier?

texts:
Can anyone explain me in details why does the following statement hold true in Chaum and van Antwerpen scheme for undeniable signature?

  The probability that a dishonest signer is able to successfully
  mislead the verifier in either verification or disavowal is 1/q where
  q is the prime number in the signer's private key

Chaum and van Antwerpen scheme:

1) Initialization

Select two big primes $p$ and $q$ such that $p - 1 = 2q$
Select a generator $g$ of the cyclic subgroup $G$ with order $q$ inside of $Z_p^*$

which means an element $g$ such that $1 = g^q \bmod p$ and $1 \ne g^a \bmod p$ for all $0 < a < q$
Choose a private key $k \in \{1, 2, \dotsc, q-1\}$
Send to the Trusted Authority (PKI) the public scheme key $(y, g, p)$ where $y = g^k \bmod p$

2) Signature of a message $m \in G$

Compute the signature $s = m^k \bmod p$

3) Verification of a signature $s$

The verification phase is characterised by a challenge / response procedure between the verifier (Victor) and the author of the signature (Sally):

Challenge:

Victor chooses two random numbers $a,b \in \{1, 2, \dotsc, q-1\}$
Victor computes the quantity $c = s^a y^b = s^a g^{kb} \bmod p$ and sends it to Sally

Response:

Sally computes the response $r = c^{k^{-1}}$ where $k^{-1}$ is the number such that $kk^{-1} = 1 \bmod q$ and sends it back to Victor

Final verification:

Victor checks if $r = m^a g^b \bmod p$ holds true, if it does then the signature is authentic, otherwise or the signature was forged, or Sally is trying to deny her signature.

Which of the two possibilities holds true may be checked with an disavowal procedure that I'm not explaining cause it should not be of interest for the question.

For any further details about the scheme read the following chapter of Handbook of Applied Cryptography at page 476


texts: The existence of two-round zero-knowledge proofs

texts: Does there exist any (im)possibility results for two-round private-coin non-auxiliary input zero-knowledge proofs for languages outside BPP?


texts: SHA-1 – Why is it hard to find a certificate collision?

texts:
Why is it it’s so much harder to execute a successful collision on certificates than it is on text data?

I assume this has to do with the fact the certificate actually is a file that contains signed (and therefore encrypted) data. However, why does this complicate things? Of course an attacker doesn’t possess the private key but why would this make a difference from a technical point of view?

I already read there’s several ways to find collisions. The goal is to find the path of the least resistance (in "reasonable" amounts of time). The only successful MD5 certificate collision I was able to find is a “chosen-prefix” collision. In this case they were also depending on the probability of some of the functions of the CA, like the serial number counter, the time between request, processing and issuing and the amount of certificates issued on average.

In this scenario it’s necessary to have a CA that (unknowingly) cooperates in the process (which isn’t a requirement with non-signed files. If this is the case, then we should be safe. Because:

No collision can be made after the certificate has been generated;
All CA’s only issue SHA-2 certificates;
(both are assumptions but in the ideal world scenario)

Does it actually work out like this?


texts: AES-CBC then SHA vs AES-GCM for encrypting and authenticating a web token

texts:
I am trying to have something like JWT but kinda ad hoc and encrypted. The token itself is simply a stringified JSON that contains the user ID and Unix timestamp.

Now, I tried to use AES-128-GCM, however I did some simple modification in the ciphertext before decrypting, just appended some bytes to the ciphertext, and found that it decrypts successfully, does that mean that those bytes were counted as padding and that AES GCM is authenticate then encrypt algorithm?

I feel that encrypt-then-authenticate feels more secure to me. Also, is AES GCM authentication even secure enough to be compared to SHA256 for example or is it CRC tier for quick integrity and cannot be used for secure authentication like HMAC?

In other words: is AES-128-CBC then SHA-256 more secure than AES-128-GCM?


texts:
Let $q$ be a given random prime of $2b$-bit for some security parameter $b$ (say $b=128$); let $p$ be a given much larger random prime with $p=q\cdot r+1$. Let $(G,*)$ be the (Schnorr) subgroup of $\mathbb Z_p^*$ with $x\in G\iff x^q\equiv1\pmod p$. Assume $p$ is large enough that the Discrete Logarithm Problem is computationally hard for a(ny) generator of $G$, that is requiring effort $O(2^b)$.

Starting from a given hash $H$ conjectured computationally secure in the random oracle model (say SHA-256 or SHA-512), we want to construct a public, easily computable hash $\hat H$ with result in $G$, computationally secure in the random oracle model, and such that for any generator $g$ of $G$, it is computationally hard to exhibit $m$ and $x$ with $g^x\bmod p\;=\;H(m)$.

Does $\hat H(m)\;=\;H(m)^r\bmod p$ qualify? If yes, what formal argument can we give (perhaps making some plausible hypothesis), and how wide does $H$ needs to be? Otherwise, what's a simple alternative?

Note: I'm willing to tolerate the issue that $H(m)^r\bmod p$ has a small chance to be zero, which is not a member of $G$, since it is computationally impossible to exhibit an $m$ with this property.

Motivation: I'm trying to simplify my laborious construction of $H_2$ in that answer.


texts: What does "Clocked" mean in alternating step generators

texts:
In the wiki article, it says "An ASG comprises three linear-feedback shift registers, which we will call LFSR0, LFSR1, and LFSR2 for convenience. The output of one of the registers decides which of the other two is to be used; for instance, if LFSR2 outputs a 0, LFSR0 is clocked, and if it outputs a 1, LFSR1 is clocked instead."

I would appreciate it if someone could explain how an ASG works and what it means for the LFSR to be clocked or left alone and if possible, a small example to show this.


texts: Check if two anonymously signed messages have the same author

texts:
I need digital signature scheme with following rules:

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

For example:

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


texts: Correctness of signle-point Oblivious PRF

texts:
In the paper Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF, Chase et al. shows that a PSI scheme can be achieved by using an oblivious PRF (OPRF). They summarized a single point OPRF protocol between a sender $S$ and a receiver $R$ that can be used to check if an element $y_R\in Y_R$ has an equivalent in the set $X_S$ as follows:

Let $F(\cdot)$ pseudo-random code that produce a pseudorandom string, and $H$ be a Hash function
Let $a\cdot b$ denotes the bitwise AND operation between $a$ and $b$, and $a \oplus b$ denotes the bitwise XOR operation

Sender $S$
Receiver $R$

 Sample $s \xleftarrow{$} \{0,1\}^\lambda$
Select and input $y_R\in Y_R$  Sample $r_0 \xleftarrow{$} \{0,1\}^\lambda$ and compute $r_1 = F(y_R)\oplus r_0$

$S$ and $R$ engage in $\lambda$-times OT protocol in which $S$ is the receiver and $R$ is the sender. At each step $i\in \{1,\dots,\lambda\}$, $S$ sends the choice bit $s[i]$ to the OT, and $R$ sends $r_0[i], r_1[i]$ as inputs to the OT. The OT returns $r_{s[i]}[i]$ to $S$.

Once the $\lambda$-time OT is terminated, $S$ sets $q$ as the ordered concatenation of $r_{s[i]}[i]$ received, i.e., $q=r_{s[1]}[1]\mid\mid \dots \mid\mid r_{s[\lambda]}[\lambda]$.

$S$ sets $k=(q,s)$ and define the OPRF as: $$OPRF_k(x)=H(q\oplus[F(x).s])$$

In the video presentation of this paper, the authors said that, after the OT exchange, $q$ is in fact equal to: $q=r_0 \oplus[s\cdot F(y_R)]$. So if the input $x$ given to the $OPRF$ function is equal to $y_R$, we have: $$OPRF_k(y_R)=H(q\oplus[F(y_R).s]) = H(r_0\oplus[s\cdot F(y_R)] \oplus [F(y_R).s]) = H(r_0)$$

My question is the following: why after the OT protocol, $q=r_0 \oplus[s\cdot F(y_R)]$?


texts: Symmetric-like cyphers with several steps

texts:
Are there any good symmetric-ish cyphers that involve three or more steps with independent key material for each step?

Formally, there should be a function $K(s)$ that returns a tuple $(k_1,..,k_n)$ and a function $P(k,d)$ such that if $d_i = P(k_i,d_{i-1})$ then $d_n=d_0$ but there are no known relationships between strictly fewer than $n$ of the $k_i$.

Stream cyphers provide this for $n=2$ of course, as the independence requirement becomes vacuous, but I'm unaware of anything with $n>2$ that's both secure and efficient as a symmetric cypher.

It's okay if we replace $P$ by another operation $P'$ for the $i$-th step for preferably at most one i but we do not want any relationship between $k_i$ and $k_j$ for $j \neq i$.

One could use secret sharing algorithms, or simply XOR, to do this quite securely, but that'd require key material as big as the original file, making it inefficient.

There are tricks for doing roughly this with asymmetric systems like elliptic curve scalar multiplication, but that's too slow for my purposes.


texts:
Is it possible to make ElGamal IND-CCA2 using OAEP or OAEP+? (OAEP+ from: "OAEP Reconsiderd" by Shoup)

The reason I ask is that I recently answered this question and it came to my mind that OAEP or OAEP+ might be possible solutions.

Note this isn't a practical question at all. There's no intention in implementation, I'm just asking if it would be secure if I would implement it.


texts:
I'd like to use the output of a pseudorandom function (PRF) as a one time pad.

I want to use AES-128  (as it's commonly used as a PRF). As we know AES-128 output 128 bits.

Question: Would be secure to truncate the output of AES-128 and get only 32 or 64 bits of it as one time pad to mask some 32 or 64 bits value respectively?


texts: How to calculate the needed encryptions in salted passwords?

texts:
Consider if a 16-bit salt is used, and it is uniformly applied over a very large password file (200,000 entries). An attacker wants to see if one particular password (say, "bubba") is used by any of the password entries. How many encryptions must be calculated, and how many comparisons must be made (of their generated-hash vs. stored hash values)?

Assume the attacker has the stored-hash-values, but he does not know which salt is used for any individual password hash. In other words, they can see /etc/passwd (so they know the 200,000 usernames), and have only gained access to the hash (but not the salt-portion) of what is stored in /etc/shadow.


texts:
I'm looking for commonly used and proven CPRNG implementation in C. What to use? ChaCha20 like in Linux Kernel?
Does anybody know other implementations?
PS: I don't want to implement by itself because it requires high accuracy and later must be verified by security experts to make sure all works correctly. Also I plan to use it on embedded device which OS doesn't have random system calls


texts: Differential privacy RAPPOR article proof doubts

texts:
Recently I've been trying to understand the RAPPOR proof:

\begin{eqnarray*}
P(B' = b' | B = b^*) & = & \left(\frac{1}{2}f\right)^{b'_1}\left(1 - \frac{1}{2}f\right)^{1 - b'_1} \times \ldots \\
                   &   & \times \left(\frac{1}{2}f\right)^{b'_h}\left(1 - \frac{1}{2}f\right)^{1 - b'_h} \times \ldots \\
                   &   & \times \left(1 - \frac{1}{2}f\right)^{b'_{h + 1}}\left(\frac{1}{2}f\right)^{1 - b'_{h + 1}} \times \ldots \\
                   &   & \times \left(1 - \frac{1}{2}f\right)^{b'_k}\left(\frac{1}{2}f\right)^{1 - b'_k}.
\end{eqnarray*}

but the authors have defined:

\begin{eqnarray*}
P(b'_i = 1 | b_i = 1) & = & \frac{1}{2}f + 1 - f = 1 - \frac{1}{2}f \;\;\;\text{~and~}\\
P(b'_i = 1 | b_i = 0) & = & \frac{1}{2}f.
\end{eqnarray*}

and we know that $b^* = \{b_1 = 1, \ldots, b_h = 1, b_{h+1} = 0, \ldots, b_{k} = 0\}$ (defined by the article).

Have the exponents been swapped? I have tried to recreate the proof, but the result shows inverse exponents.


texts: How do I know if a given curve requires a FpCurve F2mCurve or ECCCurve?

texts:
I'm trying to read a public key into Bouncy Castle (secp256k1) and need to choose from the following objects

        FpPoint;
        FpCurve;

or

        F2mPoint;
        F2mCurve;

or

        ECPoint;
        ECCurve;

Although it would be helpful if someone simply told me which object to use, what would be more useful is if someone can guide me through the general thought process in selecting any of the above objects for a given named curve.


texts:
I've been messing around with SEAL library for a few days and I've got a following question.
I've got a bunch of datapoints [x_1, ..., x_n], n < poly_mod_deg of type 'double' and I use batch encoding and CKKS sceheme to calculate
their average and variance. Calculating average works fine and I like the result, but I would like to calculate variance in more efficient way.
To explain what I mean:
Going into variance calculation I have following data:
Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0]) and
Encrypted([x_avg, x_avg, x_avg, ..., x_avg]) (*)
Next I calculate their difference and get something like:
Encrypted([x_1 - x_avg, x_2 - x_avg, x_3 - x_avg, ..., x_n - x_avg, -x_avg, -x_avg, ..., -x_avg]) (**)
Then I square and get:
Encrypted([(x_1 - x_avg)^2, (x_2 - x_avg)^2, (x_3 - x_avg)^2, ..., (x_n - x_avg)^2, x_avg^2, x_avg^2, ..., x_avg^2]) (***)
And then I sum first n values using n left by-one rotations and divide the result by n to finally get the variance.
-----------------------------------------------------------------

This works fine for small n. But I want to zero-out useless components at (*) or (**) or (***) so that after squaring I'd get the following:
Encrypted([(x_1 - x_avg)^2, (x_2 - x_avg)^2, (x_3 - x_avg)^2, ..., (x_n - x_avg)^2, 0, ..., 0])
I want that because then I'm able to calculate their sum using only log2(poly_mod_deg/2) sumations using technique described in https://www.youtube.com/watch?v=XaYEHnaAg8M&t=47m29s
Is it possible to achieve that in simple, secure in efficient way?
I've tried to multiply (*) or (**) or (***) by [1.0, 1.0, ..., 1.0, 0.0, ..., 0.0], where all but the first n components are zero.
It didn't work because compiler complained with 'result ciphertext is transparent' and
aborted the mission and I didn't like that solution anyway since it uses one more multiplication, which hopefully is excessive.
Increasingly desperate I also tried to copy encrypted zero from Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0]) into last components of
Encrypted([x_avg, x_avg, x_avg, ..., x_avg]).
 I did something like:
c_zero = Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0])[n+1];
while n < i < poly_mod_deg:
     Encrypted([x_avg, x_avg, x_avg, ..., x_avg])[i] = c_zero;
     i++;
But i guess this stuff just doesn't work this way, since printing out last 20 or 30 values of Encrypted([x_1, x_2, x_3, ..., x_n, 0, ..., 0]) shows no repetition.
On that note, this also probably means that i always have to inform "server-side" about the number of encrypted datapoints in ciphertext? How unsafe is that?
I didn't want to bloat the post with code, so it's here: https://pastebin.com/Uy0wdgG9. Also deleted comments from the code, since they were in my native tongue. Sorry.
Also on the chance that someone from the SEAL team sees this: great job,  fun stuff!


texts: Does Cramer-Shoup allow re-randomization?

texts:
Is it possible to re-randomize a ciphertext with the Cramer-Shoup System? I have some Cramer-Shoup ciphertexts and i want to re-randomize them, so they look different and are unlinkable to there previous form, but still can be decrypted with the original secret-key. Is this possible?

And if it is, would it still be possible using the Camenisch-Shoup System, which calculates a Proof, so someone knows that the "real original value" is encrypted, without decrypting the ciphertext?
I hope this is written clear enough
Thank you.


texts: Is there a way to turn a PGP key into its semi-prime counterpart?

texts:
From my understanding of PGP keys they use the RSA algorithms to encrypt/decrypt messages. So, I know that the RSA algorithms use a semi-prime number to encrypt/decrypt messages. So, what I was wondering is: is the PGP key that you see the semi-prime number, and if so, how do you convert it back to the number.

This is my public key (I think):

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAABAgAGBQJXUCB7AAoJEKOAQvYH1iPaycIP/0e77u0QaquZD/J5njjnnwSk
+Y9byw0a3S9h556DZPBfF37Cn1vC5LEJSYK2u9nZyeUpWP8a/+P8f0eE7ViQNAJ4
leUq5k6+OS2luWylyTKzLQnBHHxlI+HS080eRV8Yo5izE8HOXHby1sgy4J70ne/3
zPrCMn0OyiCJGuGwIqlp72y1v5NscsCJkB87pKmcwVBx5sGNXqTneKHg2rfYgQrM
9JCCO9F5/Li0bWTmfYifxom1l39VdZcioCCZgCi9YV5+c1gOBWlAfqtDsKVEUv4L
z97PPSaelD2FbSlHTRV2+jkB4feSEACjCGFSMh/AIYJlZX/d2N/Z33q2AdnV6+Ud
t7STYjxmz3W+jiRjQsm3vwm8uCjpjujpPvDDw51SmqARqAzuuZg8NCK69R4jxg4T
DPEHpYWbscwIWl1F+vXD5IxAXtJNVCcOH7fzoh23faGhpX8gRAMsFbpAQAn0arbY
idaRkVE4pfBGieN0w1md5GaARYY8pUU+39D4OsXjXajcMTklhs3hYtbsATV4Z7WT
YD+0T2XXT9XAfGA/X6j7oqzZe35L2HYrVy/yOJrcvSho+gpn5V7HPhkGYGCYZQvr
VfA7iArY3OTVSJ2GNpMm9qaQVcoInV9aYaEYB7J2e8pkZjtMFr4lCe2aXCbhGMYk
ZHOMYG21JbwhtdPJdd/U =Y2jy
-----END PGP SIGNATURE-----

Sorry, if I am totally confused and actually know nothing.


texts: Functional signatures with ECDSA Verifier

texts:
Functional signatures use some master key to create a functional signature key. The functional key can be used to sign messages, but only if the message is accepted by some predicate function. For example if Bob is Alice's assistant, she can let him sign documents under her credentials, but only if the document contains the string "Signed by Assistant." Bob can then send to Veronica, who can be sure that Alice (functionally) approved this document.

The paper establishing functional signatures is found here. In their construction (found on pages 18-19) they rely on an underlying public key signature scheme, and a non-interactive zero-knowledge proof (ZKP). Specifically the verification step is running ZKP verification with a) function output, b) the ZKP proof, and c) the common reference string (CRS).

However consider if Veronica is not capable of running the ZKP verification routine. Veronica can only verify in the underlying signature scheme (let's assume ECDSA). Maybe she's stuck in her ways and refuses to install ZKP software. Or she's a resource constrained embedded device. Or she's a popular blockchain protocol that has to maintain backwards compatibility.

Either way we're stuck having to verify signature with a client who can only run ECDSA. We are free to give Veronica new function-specific signing keys at the outset. I.e. she doesn't have to verify with Alice's master signing keys. If it helps, we can even give her some not too-large N of keys and verify with an M-of-N signature. We're also flexible with whatever ZKP protocol is used: ZK-SNARK, NIZKAoK, Pinnochio, etc. The signer also has nearly unbound computational resources.

I have a couple of half-baked ideas here. One is to use signature aggregation. Maybe there's a way to covert aggregate the CRS, function circuit, and master signing key into a single functional signature. Another possible approach might be to use an elliptic curve based ZKP protocol, like Pinnochio, and pair that to the ECDSA curve. Finally maybe a constrained private pseudorandom function (PRF). The PRF itself could just puncture when the function matches and output the signed ECDSA message. The circuit would have to contain the master signing key, but if the circuit's garbled its inaccessible (?).

Is there anyway for the original functional signature scheme to accommodate these constraints? Are any of my above approaches anywhere in the vicinity of what's needed? Or am I just barking up the wrong tree here.


texts: block cipher algorithms with variable block lengths

texts:
Rijndael supports block lengths of 128, 192 and 256. AES does not but Rijndael does.

What other algorithms support variable block lengths? Or is Rijndael unique in that regard?


texts: Key Confirmation Attack [Key Distribution Center (KDC)]

texts:
Okay this is how I understood it according to this:

Alice $A$ establishes a connection to $KDC$ and prepares for session key Exchange $k_{ses}$
$A$ encrypts the request with her key $k_A(A, B)$ meaning "need a session key to communicate with Bob $B$"
$KDC$ decrypts the message, genereates $k_A(k_{ses}, k_B(A, k_{ses}))$ and sends it to $A$
$A$ decrypts the messages and got now $k_{ses}$ the session key and the other part $k_B(A, k_{ses})$ she cannot decrypt (only $B$ kan due to $k_B$).
$A$ forwards the $k_B(A, k_{ses})$ message to $B$
$B$ decrypts $kB(A, k_{ses})$ and now knows he is talking to $A$ over the key $k_{ses}$

In my slides there is an attack described - the Key Confirmation Attack - which does look like this:

The thing here is now that I am not sure how this is supposed to work. This could only work if $RQST(ID_A, ID_B)$ (I'm sorry for the diverse notation) was not encrypted. This attack cannot work if the request was encrypted by Alice in the first place.

So, are there a few things mixed up or what am I missing?

Oscar cannot produce $k_A(A, O)$ – the requesting message to generate a session key for communication $A$ to $O$ – since he does not have the key of Alice.


texts: Why does Merkle-Damgård hashing involve putting the padding at the end instead of at the start?

texts: Pretty much the title. We have that $x$ is a prefix of $PAD(x)$, instead of being a suffix - was that an arbitrary choice or is there a reason for it? Thank you.


texts: Generating unsigned, bounded random value using signed bounded random values

texts:
Use case: I have a random number generator that can generate random numbers in a range that is limited by a number $x$, say $x$ ranges from $2$ to $2^{(n - 1)} - 1$ exclusive. In this case $n$ is $16$, i.e. we can generate a number from $0$ to $32767$ exclusive. Programmers will directly identify the upper bound to be a possitive, signed value of 16 bits.

Now I want to generate a bounded number from $0$ to $y$, where $y$ ranges from $2$ to $2^n - 1$, i.e. we can generate a number from $0$ to $65535$ exclusive. Yes, this is an unsigned value of 16 bits. Is there an algorithm that can do this efficiently? Loops are allowed; the random in the range $0$ to $x$ may be generated repeatedly.

If this is not possible, I have no problem allowing $0$ to $65533$ exclusive because $32766 * 2 = 65532$ and generating $65533$ and $65534$ could significantly increase the complexity.

All generated random values must have a uniform distribution.


texts: Practical necessity of semantic security under chosen plain text attack (CPA) in CBC mode

texts:
I was not able to understand why we practically need a CPA security in Cipher Block Chaining. (which insist on having a random IV), let say if the encryption is not CPA secure i.e , the adversary can identify two cipher-text are same and conclude the two plain-text would have been same. of what use this information is for adversary. i see he is able to know that both the message are same , so what? i think he can't find the plain-text.

In other words is CPA security is strictly a academic definition of security. Does in practice attacker can extract the plain text out of this?


texts: What does the number 256 in pairing curve BN256 indicate?

texts:
There are many pairing based elliptic curves like MNT curves, BN curves, SS curves etc., When we say BN256 curve, what does the number 256 indicate? Is it some group order or number of bits required to represent some group?
How to figure out number of bits needed for representing each group G1, G2, and GT for curves like MNT224, BN256, SS512 etc.?


texts: Difference between hash functions and algorithms?

texts: Wikipedia lists "Hash function algorithms" within the "Hash function" page. I'm wondering what are the differences and if I can use the terms "hash(ing?) algorithm" and "hash function" interchangeably.


texts: Is it possible to alter the plaintext message without altering the ciphertext?

texts: Is it possible to alter the contents of a plaintext message without altering the ciphertext? Altering the private key is allowed to accomplish this. If the answer is yes, how would I go about in doing this? Encryption strength is not particularly important.


texts: Does the MixColumns step come before or after AddRoundKey in AES decryption?

texts:
I found these images depicting the AES decryption process:

In the first image, the MixColumns step comes before the AddRoundKey step, while in the second image, the AddRoundKey will come before the MixColumns.

Which order is the correct one?


texts: Practical strength of non-2^n RSA key lengths

texts:
It has for many years been popular to use RSA keys that have lengths that are powers of two. E.g. 1024-bit, 2048-bit and 4096-bit key lengths are all popular for use with OpenPGP implementations such as GnuPG, and with OpenSSH, etc, and these key lengths are often either defaults in the software generating the keys, or are recommended by organisations whose participants are required to generate keys (e.g. Debian).

I have heard it said that, because cryptanalysts in practice will have devoted more resources towards breaking keys with popular lengths, and because popular lengths are powers of two, choosing a key length that is not a power of two would provide a practical security advantage, even if this means choosing a slightly shorter key length than one would otherwise desire (e.g. 4093-bit key instead of 4096-bit).

Is there any sense in that saying? Put another way, what (if any) are the reasons for which a cryptanalytic attack that would succeed against a 4096-bit key would fail or take significantly longer against a shorter key whose length is not a power of two?


texts:
We would like to encode ECDSA Public Key specifically keys generated using the ed25519 for storage .

What is the best and less error prone method , for now we think about using Hex strings or Base64 are there other encoding schemes that can be used ?


texts: Bridging the gap between security proofs and "real-world" security

texts: I've been studying cryptography for a little while. I understand fairly well the nuts and bolts of security proofs, but I'm having trouble reconciling the formal statements of security in these proofs with their practical "meaning" for a real system. Is there an intuitive way to reason about the "real-world" security of some cryptosystem based only on a formal proof of security against a constructed adversary?


texts: Are developers expected to implement Diffie-Hellman key exchange themselves?

texts:
I noticed that the GO standard library has some really nice functions for performing AES encryption / decryption in various modes.  However, I couldn't (yet) find anything for Diffie-Hellman key exchange.

I'm not sure if I should proceed by searching more carefully, switching to a different language with a more extensive crypto library, or trying to implement the key exchange protocol myself.

The protocol "seems" implementable:

Alice sends $g^a \mod p$ to Bob
Bob sends $g^b \mod p$ to Alice
We need to choose $g, a, b, p$ appropriately

But I'd bet that there are a lot of subtleties buried in that "straightforward protocol" (for example, we need some out-of-band mechanism to defend against man in the middle attacks).

Plus, one of the first lessons of crypto is don't implement cryptographic primitives yourself, and I don't know if this warrants an exception to that lesson.

Are developers generally expected to implement Diffie-Hellman key exchange themselves? If so, what are the primitives that I should be using, and where can I find a good reference for some of the subtleties that should be considered?


texts: Can I use HKDF to improve security of HMAC used with weak hash function?

texts:
I am writing a framework which encrypts/decrypts files (or streams, in general) with symmetric key using block cipher (for example, AES). To authenticate encrypted file, I use HMAC, which is initialized with a key derived from supplied password (using PBKDF2 and then HKDF function). It is calculated during encryption phase (I first encrypt, then HMAC). The result of the HMAC function is placed in the header of the encrypted file. On decryption, I check HMAC of the encrypted text. If calculated HMAC and HMAC from the file header match, then supplied password is correct and encrypted text is not corrupted.

My question is about hash function that is used with HMAC. Obviously, the best solution would be just to use some strong hash function (like SHA-256). However, I am experimenting with a thought of using weaker, but faster function, because I would like to improve performance of my framework (SHA-256 is not the fastest one). Using weaker hash function for HMAC does not necessarily mean that HMAC is affected. For example, Bruce Schneier wrote that broken SHA-1 does not affect HMAC.

What about using HMAC with MD4? From various sources I have learned that it is NOT recommended. But what if instead of plain HMAC/MD4 I use PBKDF2_MD4 as input for HKDF function, which takes PBKDF2_MD4 output as its input (e.g. as PRK) and expands entropy? Then I can retrieve this expanded entropy and use it (for example, first 16 bytes, whatever) instead of original HMAC output to authenticate encrypted file.

My question is - if HMAC_MD4 is considered insecure, is HKDF(PBKDF2_MD4) is also insecure? If MD4 is definitely a no-go, what about MD5?

I have read this paper on HMAC security based on various hash functions (including MD4, MD5 and others), which says that using these weak hash functions allows to perform a forgery attack. In my case, I am not concerned with forgery. I just need to verify that encrypted text is not corrupted and can be decrypted with the password provided. Obviously, using weaker hash function must not help an attacker to recover the password or, in general, get access to the unencrypted text.

Thank you for your attention.


texts: Reykeyed AES in CTR mode as a stream cipher

texts:
Suppose one uses AES in CTR mode to generate a keystream, but every $l$ bytes the $n$ bits that would follow are used as a new AES key.

Assuming that AES is a secure PRP:

Is this a secure stream cipher?
How does it compare to standard AES-CTR?
Suppose the (original) key is mixed back in at each rekeying useing a one-way pseudorandom compression: what changes?

Note that AES is used as an example secure block cipher.


texts: Is HTTPS encryption using the RSA algorithm?

texts:
According to this article HTTPS and RSA is the same thing: https://tiptopsecurity.com/how-does-https-work-rsa-encryption-explained/

From other sources I learn that they are both asymmetric encryption methods.

What is the difference between the two?


texts: Inverse of a polynomial using long division over GF(256)

texts:
I am trying to find the inverse of a polynomial $3x^3+x^2+x+2$ over the field $GF(2^8)$ with polynomial $(x^4-1 )$

Here is what I did,

$$ \dfrac{(x^4-1)}{3x^3+x^2+x+2}$$

$$ (x^4-1) = (171x+199)(3x^3+x^2+x+2)+ (142x^2+227x+115)$$
$$ \dfrac{(3x^3+x^2+x+2)}{(142x^2+227x+115)}$$

But I can not divide further because 142 does not provide me odd multiples to cancel $3x^3$. Can I use fractional number to get rid this? I tried fractional number too, but they made its too much complicated.

How can I do this? Or I am following a wrong approach?


texts: Why are zk-SNARKs possible, in layman's terms

texts:
zk-SNARK: Zero-Knowledge Succinct Non-interactive Argument of Knowledge

From the Ethereum blog:

  One natural use case for the technology is in identity systems. For example, suppose that you want to prove to a system that you are (i) a citizen of a given country, and (ii) over 19 years old. Suppose that your government is technologically progressive, and issues cryptographically signed digital passports, which include a person’s name and date of birth as well as a private and public key. You would construct a function which takes a digital passport and a signature signed by the private key in the passport as input, and outputs 1 if both (i) the date of birth is before 1996, (ii) the passport was signed with the government’s public key, and (iii) the signature is correct, and outputs 0 otherwise. You would then make a zero-knowledge proof showing that you have an input that, when passed through this function, returns 1, and sign the proof with another private key that you want to use for your future interactions with this service. The service would verify the proof, and if the proof is correct it would accept messages signed with your private key as valid.

I bolded the parts which seem impossible to me intuitively. I found some research papers with very technical explanations, which I don't understand. Could someone explain why this is possible, in layman's terms? Intuitively it seems like there would be plenty of ways for the client to alter the program code in order to produce output which could be used to fake their identity.

Some documentation and code


texts: What is the computational cost of guessing symmetric keys for two ciphers that decrypt to the same input?

texts:
A message m is encrypted with two symmetric keys, resulting in two ciphers c,

c1 = encrypt(m, key1)

c2 = encrypt(m, key2)

What is the computational cost of guessing symmetric keys for both ciphers that decrypt to the same message?


texts:
Please consider the following question:
Determine the order of all the elements of the following multiplicative groups. You can write a C or Java program to do this.
a. $Z_{21}^*$
b. $Z_{23}^*$

Now note that $21$ is not a prime number and since the question refers to a
multiplicative group, I would expect that means the operator for the group is
multiplication mod 21. This means that the number $7$ should have an inverse. That is, there should be a number x, such that $(7x)\,mod\,\,21\,\,=\,1$. I claim that no such $x$ exists. What am I missing?

Bob


texts:
The inversive congruential generator over the prime field $k=Z/pZ$ is given by the iterations of the map $x\mapsto a/x+b$ if $x\neq 0$ or $b$ if $x=0$.
One can choose $a,b$ in $k$ such that the orbit length of the iteration is exactly $p$. My question is very simple:

Is the Inversive Congruential Generator actually used in Cryptography? Is there any known attack against it?


texts: Can you help me understand Pollard's rho example?

texts:
I'm studying the Pollard's rho algorithm to solve discrete logaritms on the Handbook of applied cryptografy but I didn't understand one part of the theory and looking at the example gets me more confused.
This is the example

The first thing that I don't understand is how do you know that an element is on $S_1$ or $S_2$ or $S_3$ (in general not in in this example because is explained)and the second thing is: where did he get mod 3?


texts: Fastest / easiest way to find rotor wiring without physical inspection on Enigma Machine emulator

texts:
We have an Enigma machine emulator we are trying to replicate. Machine has 3 rotor positions and 6 rotors that can be selected. The input goes through 3 rotors then is reflected back to start as is typical.

How can we find the rotor wiring? We are thinking that imputing the same input 26 times while holding the second and third rotors in fixed position is something to do with it (so we get a full rotation of the first rotor). However after this point we are getting a bit stuck. We have tried to simplify this into a 4 letter alphabet to simplify the whole procedure as a test but still are unable to find the wire position.

Unfortunately it's all in software or we could simply remove the rotors and get them with a multi-meter. Is there a better way to find the wiring?


texts: montgomery reduction multiplicative identity

texts:
How do you figure out the multiplicative and additive identity with respects to R?

I pick some R such that gcd(R, N) = 1 where N is the size of the group.

Given some field element x in the group, I do x' = xR mod N

How would I figure out the multiplicative identity m such that x' * m = x'

and the additive identity a such that x' + a = x'` ?


texts: How can I store confident data with OpenID?

texts:
I want to make a system that needs to store some confident user information in a database. I intend on using OpenID for user authentication.

I would like encrypt the data in a way that it can only be decrypted when the user is logged in. What are the most common approaches to storing user's data securely in such a setup?


texts: Encrypt-then-HMAC implementation - am I doing it right?

texts:
I want to implement authenticated encryption using C#.  There is a dot net class called encryptAndAuthenticate, but it is only supported on windows 8 or later, and I need the code to also work on windows 7.  In other words, there is no built-in dot net library to do AES in GMC mode that works on windows 7 or earlier. So it looks like I have to use separate calls to the C# aes and hmac routines.  Here is the pseudocode in my head.  Am I planning this correctly?

Encryption:

User supplies plaintext.
User supplies password.
CSPRNG generates 256-bit salt.
Slow key derivation function on password and salt produces 640-bit output.
First 256 bits of output becomes AES key.
Next 128 bits of output becomes AES IV.
Last 256 bits of output becomes HMAC-256 key.
AES encrypt CBC mode using (plaintext, AES key, AES IV) to produce ciphertext.
HMAC-SHA256 on IV||ciphertext (using HMAC-256 key) to produce MAC.
Publicly store salt, ciphertext, and MAC.

Decryption:

User retrieves salt, ciphertext, and MAC.
Step 2 from above.
Steps 4-7 from above.
Step 9 from above.
Compare calculated MAC to retrieved MAC.
If different, abort and tell user decryption failed.
If valid, AES decrypt CBC mode using (ciphertext, AES key, AES IV) to produce plaintext.
Display plaintext to user.


texts: Proving a function is a one way function

texts:
I am trying to prove that a function is a one-way function.

The function I am working on in particular is $f'(x,y)=f(x)||f(x \oplus y)$.

For what I have understood looking at similar solved solutions (e.g. 1c), the strategy is the following:

Assume $f'$ is not one way, so exists an $A'$ that can invert $f'$ with non-negligible probability
Use $A'$ to construct $A$ that can invert $f$.
Show that $A$ inverts $A$ with non-negligible probability
Contradiction.

Based on this knowledge, I am trying to prove the given

$$f'(x,y)=f(x)||f(x \oplus y)$$

So, here is my attempt:

Assume $f'(x,y)$ is not one way function
So, exists a $A'$ that can invert $f'$ probability
Construct

$A(z)$:

pick a $w \in f(x)$ (for any $x$)
$x,y <- A'(f(z, y)) = A'(f(x) || f(x \oplus w))$
we have now inverted the first half
...
return $x,y$

However, although I understand the method I cannot find any valid way of making the construction:

How can you build such construction?
Is there something I am doing wrong? or am I in the right direction?


texts: How does Signal Messenger's Safety Number Works?

texts:
Why do they recommend the user to verify the 60 digit code in person or via other medium of communication.

How is the security code generated and work on Signal and Whatsapp Messanger?


texts: Twofish vs. Serpent vs. AES (or a combo)

texts:
I've seen some posts and info online, but they are from 2009, 2010, 2011 or 2012, which is 3-6 years ago, which is a very long time. So I'm looking for an up-to-date answer about which of these is the safest encryption to be used, or rather most unbreakable? Particularly interested in encryption programs, so performance would also interest me, not only security.

I think things have changed since Snowden's postings, though then again - I know that a file encrypted with some sort of TrueCrypt algorithms remains uncracked after a few years of trying in the FBI.

So, having that in mind, I'd like to know more about it all so that I would be able to choose the right algorithm for me.


texts:
I would like to know if there is any research work using CP-ABE for threshold cryptography?

I want to know also if applying CP-ABE for threshold cryptography would overcome other techniques.


texts: The correct use of the term "TLS session"

texts:
TLS consists of sub-protocols including the handshake where the key-exchange is and the record protocol. If I want to use a statement like:

  both parties negotiate a ciphersuite that defines the algorithms that
  will be used in the session

Is this a correct statement? Can I use the term session in a context that includes the key-exchange? The term session gives me the impression that it is after the key-exchange has been done. However, I use it in my statement because I am not sure if the ciphersuite defines anything beyond the key-exchange?

Need more clarifications please.


texts: Why is the block cipher in the CBC-MAC taken to be a pseudo random permutation (PRP) and not a pseudo random function (PRF)? We don't need the bijective property of the PRP. So why go with it?


texts: Bit-strength of discrete logarithm for a group of integers modulo a safe prime

texts:
Preliminaries

Let $p$ be a safe prime number.
Let $\mathbb{Z}_p^*$ be the multiplicative group of integers modulo $p$.
We have $\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}$ .

Let $g \in \mathbb{Z}_p$ be a primitive element of $\mathbb{Z}_p$ .
Let $h$ be an element of $\mathbb{Z}_p$ .

We define the Discrete Logarithm Problem for a group of integers modulo a Safe prime (DLPS) as:

  DLPS: Find the integer $k$ such that $\;\;1 \le k \lt p\;\;$ and  $\;\;g^k \equiv h \pmod p$ .

We assume that the best algorithm to solve DLPS is the Number Field Sieve for Discrete Logarithms, which has an expected running time of
$$L_p\left[1/3, \sqrt[3]{64/9}\right] \,=\; e^{\textstyle \left(\sqrt[3]{64/9}+o(1)\right)\big(\ln p\big)^{1/3}\big(\ln \ln p\big)^{2/3}}$$

Questions

If we choose $p$ to be a 2048-bit safe prime, which is at least equal to $2^{2047}$, then the expected number of arithmetic operations needed to solve DLPS is approximately equal to:

$$e^{\textstyle \left(\sqrt[3]{64/9}+o(1)\right)\big(\ln 2^{2047}\big)^{1/3}\big(\ln \ln 2^{2047}\big)^{2/3}} \\
\approx \, e^{\textstyle \big(1.923\big)\big(1419\big)^{1/3}\big(7.258\big)^{2/3}} \\
\approx \, e^{\textstyle \big(1.923\big)\big(11.24\big)\big(3.749\big)} \\
\approx \, e^{\textstyle \big(81.00\big)} \\
\approx \, 2^{116.9}$$

Is it correct?

Should I make sure that $(p+1)$ has a large prime factor? (to make $p$ a strong prime)

If I am not mistaken, this is the graph showing the security level of DLPS in function of the size of $p$:

Edit 7th June 2019: Here is the context in which I will use this discrete logarithm problem:

Context

I am creating an online massively multiplayer video game. In this game, the player moves around a character and performs actions in a persistent virtual world. I use the discrete logarithm problem as an in-game currency. Every action performed by a character (move around, buy an item, throw a projectile, etc.) has to be paid by the player with CPU time. This way, I don't have to spend my time monitoring players to detect cheaters (multiple accounts, farming bots, etc), because what cheaters usually do is explicitly allowed in my game.

Here is how it works: to earn the right to perform an action in the virtual world, the player requests a discrete logarithm challenge to the game server. Then, the server generates random values for the generator $g$ and the exponent $k$, computes the result $h \equiv g^k \pmod p$, and send the values of $g$ and $h$ to the player. Then the player's client computes the value of the exponent $k$ and send it back to the server to receive credits.

The value of $p$ will never change, and the values of $g$ and $k$ will be different for each challenge. The player can choose the difficulty of the challenge by setting an upper bound on the bit-length of the value of the exponent $k$ (the amount of credits earned is proportional to the amount of CPU time spent).


texts: What does "birational equivalence" mean in a cryptographic context?

texts:
In a recent question on using the same curve for signing and ECDH it was noted for the Ed25519 curve and Curve25519:

  Nitpick: the curves are birationally equivalent, not isomorphic.

Now this term shows up quite often in cryptography, especially when one is concerned with the differences and transformations between various curve representations. So my question:

For a "cryptographer" who has never heard of "varieties" or "functional fields" what does "birational equivalence" state for the relation between two groups / rings / fields?

I have searched around a bit but usually most explanations use this advanced algebraic terminology and I'd just like to have a "simple" explanation / intuition for the day-to-day algebra in cryptography.


texts: Using a hash with a constant key to create easily verifiable codes

texts:
I'll keep my question short. If I keep handing out different codes generated by this function, will it be trivial to figure out the secret key?

secret_key = {random bytes}

function generate_code(parameters)
  return sha256(parameters + secret_key)

I know little about these things. What I like about this function is that it's trivial to verify if a code is valid given the same parameters. If this is a bad way of achieving this, what is a better way?


texts: An example of Knapsack Cryptosystem cracks/attacks?

texts:
I have been studying papers on various ways to crack the knapsack cryptosystem, unfortunately the mathematics in these papers involves lattices and LLL which is over my head.

The paper "New Attacks for Knapsack Based Cryptosystems" may have a Sage example but I can't view the paper.

http://www.math.ucsd.edu/~crypto/Projects/JenniferBakker/Math187/index.html#Anchor-Cryptographi-62216 has an example but I can't seem to follow it.

I tried writing my own python code based on pseudocode in one paper but it seems to require a loop of 2**256 and neither I nor the atoms in the universe plan on living that long...

I was wondering if anyone could help me with this. Example sage code would be perfect, source code in any language would work as well.

Thanks!


texts: In cryptographic protocols, what protects against an attacker dropping messages?

texts:
In some cryptographic protocols I have seen messages protected for confidentiality, authenticity, replaying attacks, reordering attacks, etc.

What protects a protocol from an attacker in a privileged network position (e.g. in control of a majority of the fibre networks connecting countries) from just dropping messages altogether, thus stopping the two parties from communicating (a “Denial Of Service”)?

For example: if a protocol includes a sequence number, the receiver sees messages #233, #234, and #236. What should the receiver do if they missed receiving the #235 message?


texts: How do voters verify a Helios (v3) election result?

texts:
So from my understanding of verification specification version 3, a Helios election proceeds as follows:

A voter retrieves the system's public key to encrypt their vote & submit it. The voter gets a fingerprint representing their vote.
When the election period is over, a list of all names & their fingerprints are made public so that an individual voter can see that their vote is in the list correctly
Using the homomorphic properties of the encryption algorithm, all votes are summed
A couple of key people are selected to watch as the private key is used to decrypt only the final summed result, proving that it was done with all votes counted correctly

Questions:

How does an average voter know that his vote actually counted? He doesn't have any way of performing the summation and obtaining the private key to decrypt.
If at the end of the election the private key is made public, then is knowing the list of fingerprints alone enough to calculate the result themselves? I assume no, otherwise individual votes would be known after the fact.
How does the summation process prevent someone from submitting a value outside the range of allowed values, unless they decrypt each individual result... which I thought was the whole point of the homomorphic encryption to not do that?


texts: Using AES-GCM (or AEAD ciphers in general) as a pure MAC without encryption

texts:
What's the opinion on using an AEAD cipher such as AES-GCM for example as a pure message authentication code (MAC) when only message authentication but not encryption is required.

does it bring any benefits?
does it have any obvious disadvantages?
does it have any security implications?


texts: How is R-LWE related to lattice cryptography and homomorphic encryption?

texts:
Can someone tie everything together for me? I'm interested in H.E and I have some background in AES, DES, RSA and the like. While reading around I stumbled on Shai Halevi's course on lattice cryptography as well as Vaikuntanathan's course.
Looking around I found Fully Homomorphic Encryption from Ring-LWEand Security for Key Dependent Messages which didn't really help me solidify the concepts I'm learning.
I "know" that lattice cryptography revolves around lattices and finding shortest vectors which is thought to be(?) NP-hard. I also found Homomorphic Encryption, LWE, and Practical Applications but it seems the asker there is ahead of me in terms of understanding how everything ties together


texts: Which protocols / file formats use CBC with a random IV and without a MAC?

texts:
Disclaimer: I am a noob so this may well be a stupid question or one that's been asked before. I didn't see it come up after searching, though, so I'm going to assume it hasn't been asked here.

The question's pretty much covered in the title. An explanation of why is below.

Why?

Short version: Because CBC is malleable and I didn't realize that was already known, nor did I know the term for it. I do know the term, now.

In any case, I'm leaving the longer-form explanation of that below because I wrote it and, hell, it may be useful to someone.

I was reading this helpful wikipedia article on CBC, when I realized something which I found kind of... horrifying...

The IV isn't encrypted using the block cipher algorithm, and it's XOR'd directly with the plaintext. So, if you:

know / can guess what some of the bytes in the first block of plaintext will be, and
you can modify the IV

then you can flip bits in the decrypted plaintext of the first block by flipping the bits in the corresponding positions of the IV. The block cipher algorithm is completely irrelevant because you're bypassing it entirely, and as far as the end-user is concerned there's no way to tell tampering occurred.

Or, put another way, if byte 5 in the IV is 0xcd, and you're pretty sure byte 5 in the first block of input will be 0x41, then to ensure that byte decrypts to 0x97 in the final output, you'll just need to change byte 5 in the IV to $(0x97 \oplus (0x41 \oplus 0xcd))$ (the order of operations is irrelevant, but the last two terms are grouped because they will clearly cancel).

Now, as I see it, there are two easy mitigations for this:

encipher the IV, or
use a MAC with the message

However, it's worth noting that the first mitigation is only really meaningfully helpful IFF you know the person doing the decrypting will:

be able to verify the MAC, and
ignore every block after a corrupted block

Otherwise it's useless. Because the problem is fundamentally that CBC allows you to bypass plaintext at any point in the block chain by flipping corresponding bits in the previous block's ciphertext. If I have a pretty good idea what'll be in block 39, byte 12, and I know either:

blocks won't be accessed in-order, and the person's likely to access block 39 before block 38, or
blocks which fail to decrypt successfully will be ignored

then I can flip bits in the ciphertext of block 38, byte 12, knowing how that will affect block 39. If the thing being decrypted is software, an encrypted filesystem, or an encrypted database it's likely that blocks will be accessed out-of-order.


texts: Side channel security of HMAC in software

texts:
Assume we have a processor with a symmetric co-processor that supports AES. This processor does however not provide co-processor support for hash algorithms such as SHA-1 or SHA-256.

I've got the following strongly related questions:

Would an HMAC implementation based on a hash implementation in software - which is not explicitly protected against side channel attacks - be vulnerable to side channel attacks?
If so, are there reasons why such an attack would be stronger or less strong than e.g. a side channel attack against a symmetric cipher in CBC mode?
Would it be possible to retrieve the key used to key the HMAC algorithm?
Finally, could it be safer to opt for AES-CMAC instead in case an AES implementation in hardware is available?

It is assumed that the comparison of authentication tag values does not leak information. Both DPA and timing attacks could be considered.

The reason I'm asking is because hash algorithms are often not explicitly protected against side channel attacks. HMAC is still often used in this scenario.


texts:
Is it possible for a hash function, SHA256 for example, to be a cyclic hash function, where the hash of the hash returns the original value?
Example:
SHA256(a) = b
SHA256(b) = a

Or in another form:
SHA256(SHA256(a)) = a

A math example would be
f(x) = 1/x

because f(5) = 1/5, and f(1/5) return the original 5. f(f(5)) = 5.


texts: How does the SSH server know the length of data encrypted?


texts:
I've always been under the belief that larger block sizes require more rounds to achieve full diffusion. Rijndael, SPECK, and SIMON, for example, have a round multiplier based on the block size. The idea that a larger block size also necessitates more rounds for equivalent security also seems intuitively correct. However, reading DJB's paper introducing Salsa20, I came across the following:

  The basic argument for a larger block size, say 256 bytes, is that one does not need as many cipher rounds to achieve the same conjectured security level. Using a larger block size, like copying state across blocks, seems to provide just as much mixing as the first few cipher rounds.

This goes against what I have always thought. Why is this?


texts: MACs differ from digital signatures in the sense that MAC values are both generated and verified using a shares secret key. Does this in any way put MAC on a disadvantage as compared to digital signatures? How is one of them better than the other?


texts: Is it possible to get the PGP public key from PGP message?

texts:
Is it possible to get the public key from PGP message in PEM(Base64) format? Here is the message:
-----BEGIN PGP MESSAGE-----

hQEMA1W24kYEriipAQf9FEOPPTiqBj9kDSqCWTJmCvceU3n9oEqA7umKFYWG60nv
nWEk09AvrYK1dakfYVTKlolqV6kkxoQqt5DlsQ6YOa7I4Xfy58l9yzJQlf1KU/xN
vp3sBb8FHCkT789hZ8h9On/GoFFaDTp2rHB63ylLzcPNedlYdUS2DtooZQkt6g07
C8D0B9t66UGCGCPky0bEquihBz7u48oV+F3DVTdHV7XYCHayuMNuMAExiOv7hpRh
VauO3ryTm5R/6D06/QYAVsfrqR/UWaCdz26FQVmFc5Z9HqLaS00ppjqfktaYACNz
M88A6I0eUchpCSz8tqpURTUKdNZTjOun4pqQ+9c/TNLpAQ0uQRpuXSt1KYrbiq8l
4glvmrFqkSM/n8soDpoatjwW2BMu3IByV/OJZ1heWsxfUw/qImE5qZPxxI1CjLDe
3yGSb2SAE6l/mnfnkSPDEOxE3LRfSoOapUOc+9MtGl/gF3+TwYZ0qpXevSCOWKLz
1fnIuQU4PvWYHR3vkBuoxJ9+0aNtvr+JRsx1Wg1lNJqu6T5rQHc7ne7VocD5coi4
YyOENKDPfELi6o6/MhdFmMblTu4/AbUoErAg6zGP9CUMdYngFfNQyfFB9x2jG6fe
Pfq+g1Y6NW527Bjy8Qfd0Iy1Xz+838bvqZt5MhDXTWW+YYcPm5htL+1H2o3FoQhW
qmAM577UnjVQXoL4bg046dyA0fqd5E32xGlVOXKL6RgeGouZu8V43wrQKzJhROoV
pk6T7QEUMSiBiAoZjTAg5BalpIr+G/PWj5mCI0ys75tNeH3zQOgf0+Be7Q+AkO7/
PQHR0qfWVg+9PdEfR05ciuJ6A4SiI0QtqziMmHvgc213KWGqKuYqYr22xgkqcJWP
7lFT/56zCoyiObcEPWH9WEXwYYakEPxCn/i16c4HgZVzgeJ1x04I5t//ZM9cT15g
N3EBi58ANV8BjgLaklcoxm9XjOpIlW952Y6qvwDMMh3SRNCpGsq+Ma6+zi/T6fqW
O2psDgYjQsjsDaAmdPzGeHUTWAp752rJPKbMoInA9Bb3xMjjKg==
=ioKX
-----END PGP MESSAGE-----

I sent this to someone and I was just wondering what if someone other than us knows the PGP message and wants information like the recipient's pubkey or other info.


texts: Pen-and-paper one-way function for externally-anonymous survey

texts:
When conducting surveys, an Administrator might send an Enumerator to survey a Respondent. For "sensitive" questions (e.g. about embarrassing behavior), the Respondent may be fine with the truth being revealed to the Administrator but not to the Enumerator.

Is there a way to create a one-way function/process using simple (small and cheap) physical objects such as pen and paper that isn't too time-consuming or involves complex math? Inverting the function would be too hard for the Enumerator during, or just after the survey, but the Administrator could do it later. Assume that the Enumerator can do anything quickly to uncover the answer (e.g. "accidentally" open a sealed envelope or claim non-random data is random) so long as the Administrator gets the truthful answer in the end. Assume that this is the only interaction with the survey, so no secret information has been passed among the Administrator and the Respondent. FYI: Previous questions include ones about non-computer/manual full cryptosystems and ciphers, but answers to both involve a long time to execute.


texts: Secret Sharing Scheme, with joining players, no central entity

texts:
I am facing the the following problem:
Lets assume i have a secret, $S$, I want to share it to $N$ players so that $K$ of them can cooperate in order to obtain the secret ($K$,$N$ scheme).
Is there a scheme that supports the joining of a new player where a set of $K$ players can issue a new key without obtaining the secret itself resulting a $(K,N+1)$ scheme and with no central entity meaning there is no dealer after the first dealership.


texts: Efficient attack on RSA with known padding scheme and public key

texts:
I am having some trouble with an assignment problem. I hope I can get some guidance here. The question provides us with a public key, $N$ and the padding scheme.

This is the padding scheme "Assume PIN is a positive integer smaller than $2^{16}$. Instead of directly encrypting the PIN, she writes the PIN in binary format ﬁrst, then she appends 2048 1 bits at the right most side of the binary representation of PIN. For example, integer $abcd$ in hexadecimal becomes an integer $x$"

$c = (m^e) \bmod N$

The length of both $N$ and $C$ is 923 digits of hexadecimal.

From this knowledge we are supposed to perform an efficient attack on the ciphertext by which we can recover the plaintext.

Me and my team have tried to implement multiple cca aswell as cpa techniques, however we have been pretty much unable to find any thing that would work. Of course I understand that the trick to solving this question is in the padding, but we have yet to be able to discover how to do so.

I would appreciate any help in this regard.

Edit: The value of $N$ is

0xa05bb3783769b832a2d022646c48344948282cdcd42bff414ec90f23b7e3b1b817137664f4016319586395741996245f9c2c66dee453352dc329fe54228beaa559a610114dbe902c32572e954660adbd06f8da8c770c33bb5ad15f506073ea0c50ff4e9906e16ee70d1311e0ad81896f4807282361f5b2116488de06966b571cdb15da536226378bc1fba8a3476c5809b5a274a0117b5de3e52278d39fdfa62de29f338b0453ac3af61a30dcb2975949a3d0ec2d2b7f0d2c4d2e3ef6ddefa8caad21bc16972dcecfcd5f9332373a759632f7f02c52dd424b83985eaa673ce67023366e85899729fc1d1fede02fa9c53aa01328c9108a3c5145f47ef988688f3076d49821314210d1f4db88fa836d41f3dc3960499eb46b28261aaa1515e0fb6d7481ae051b607683cbfdc18d6b692f93d6facf4002d6fa835aac4d61911b66859a81043763e1d0ef6e47f1a7a4c8d57993b0fb67b5758ed3aca9540d39e150935cdd0c320d166da65612ae78322f96853885e6a44add306a899fab2f87cf2a1d

and the value for $C$ is

0x90fdea0c662ed2cef739c491c2f391d8cf636b80144c412580c02e3262e4fa10c6e101f4c53d09619c7cb6fc9d8edfe2a676c1c128bd8e32528aff243101b9daf655bcd5460a9bf020ff4bef0f61b94304b142b6b18830b8b4d5574e8b54903de67df71f39234fdf9f66723ab1bf426d1c0a95fabae8485e9edf7f4c868ca2816398b1f46ffda2a84b5d52ff36bad829ddc2e123f86cb266256824f047fb6f6a1c7593eaf4ae5c47c6f5e633370d832345fde53324d02687a9b21e60fcefb5e2e2eb1ace969fe72afca67847acad093dec8976336ace5f135257f740f625851a3258854775a3f4f123eae1a6253b2740de37d112bca596f36e4c0d4cfc50b05643b8ec0b52619ae7d0ae990e041ba01bc149ac4a510c81e3aef3f4f2843a50f15c637e274e714c6a768e0c7d96e28a5365b64aee0315623794724573648516ebc9b0f5135a180ac3141a98f2ef0f005f6980781036c9b1c7975774708d1929d1935ae782de80722124220a9dd3fadc457d8bdb8be762b0158187ee619142637d


texts: How can we reason about the cryptographic capabilities of code-breaking agencies like the NSA or GCHQ?

texts:
I have read in Applied Cryptography that the NSA is the largest hardware buyer and the largest mathematician employer in the world.

How can we reason about the symmetric ciphers cryptanalysis capabilities of code-breaking agencies like the NSA or GCHQ given that they have performed first class unpublished cryptographic research for the last ~40 years?
What sort of computational lower bounds can we establish on an attack against these ciphers given that these agencies may have unpublished and unknown cryptanalysis techniques of equivalent utility as differential cryptanalysis (we only know about differential cryptanalysis because someone outside the NSA/IBM rediscovered it)?

For example, could we have developed a good lower bound on the ease of finding collisions in md5 without knowledge of differential cryptanalysis?

This question is restricted to symmetric ciphers.


texts: What are coding schemes for timing channels

texts:
I know we can hide information in the inter-packet delays, e.g. we can generate a code-book that each code-word corresponds to a message and is generated by realization of a specific random process.

Is there a good, comprehensive resource about coding schemes like a “Poisson process”, or other processes?

For example: if the legitimate traffic is process $A$, can we make random variables according to that process and use permutations to represent different coderwords?


texts:
I would like to create a server that would verify a public/private key pair where the private key is encrypted with a key unknown to the server.

The server should reject the keypair if the encrypted content is not the private key belonging to the public key.

Is there a way to cryptographically prove that the content of the encrypted data is the correct private key without the server having any way of decrypting the key?

A signature using the private key, sent along the keypair, to be verified with the public key is not enough since the client could send correctly signed garbage data instead of the private key and the signature would still be valid .


texts:
Assume a Player chooses a seed $s$ and he wants to prove that he uses it as a seed to CSPRNG function, where the seed is not public.
How can he prove it?

Thanks.


texts: Security equivalence proofs for breaking RSA

texts:
It is my understanding that while a practical solution to the factoring problem will definitely break RSA, it has never been proven that the security of RSA is equivalent to factoring.

In otherwords, theoretically, someone could mathematically break RSA without breaking the factoring problem.

Are there any problems for which breaking RSA would be equivalent to (besides the obvious RSA Problem)?


texts: NaCl allows decryption with the same public key as for encryption

texts:
I followed the description here:

Public-key authenticated encryption: crypto_box

and created an example that encrypts a message with Bob's public key and signs it with Alice's secret key :

cipher = crypto_box(secret_string, nonce, bob_pk, alice_sk);

The cipher text can be decrypted and verified with Bob's secret key and Alice's public key:

message = crypto_box_open(cipher, nonce, alice_pk, bob_sk);

However, the message can also be decrypted with Bob' public key and Alice's secret key:

message = crypto_box_open(cipher, nonce, bob_pk, alice_sk);

This is somehow unexpected. I couldn't find much documentation for the crypto box. What is the math behind it?

My full code to reproduce:

#include <crypto_box.h>
#include <string>
#include <iostream>
#include <fstream>
#include <randombytes.h>
#include <string>
#include <iostream>

int main() {

    std::string alice_pk;
    std::string alice_sk;
    std::string bob_pk;
    std::string bob_sk;
    std::string nonce;
    std::string cipher;
    std::string message;

    std::string secret_string = "my secret string";

    unsigned char buffer[crypto_box_NONCEBYTES];

    randombytes((unsigned char*)buffer, crypto_box_NONCEBYTES);
    nonce.assign((const char*)buffer, (size_t)crypto_box_NONCEBYTES);

    alice_pk = crypto_box_keypair(&alice_sk);
    bob_pk   = crypto_box_keypair(&bob_sk);

    cipher = crypto_box(secret_string, nonce, bob_pk, alice_sk);

    message = crypto_box_open(cipher, nonce, bob_pk, alice_sk);

    std::cout << message << std::endl;

    message = crypto_box_open(cipher, nonce, alice_pk, bob_sk);

    std::cout << message << std::endl;

}


texts: Preimage security of combined hash functions

texts:
I am struggling with a property of combined hash function and more precisely concatenation.
I have seen that concatenating two collision resistant hash functions preserves this property (same for 2nd preimage resistance). But not always for the first preimage. Indeed, some explains that if the two concatenated hash functions are dependent, the result function could be first preimage weak even if the concatenated functions are preimage resistant. I don't see how it could happen.
First image resistance:
From y=H(x), it is computationally infeasible to find any input which hashes to that output y.


texts: mCrypton - does anyone know where I can find test vectors or a reference implementation?

texts:
I am currently writing an implementation of the mCrypton lightweight block cipher (as presented in this paper). Unfortunately, the authors do not provide any test vectors. I tried to contact the authors via e-mail, but did not receive an answer, and I had no luck googling for test vectors or a reference implementation.

Is anyone here on Crypto Stackexchange aware of a reference implementation or test vectors for mCrypton? Many thanks in advance!


texts: Finding generator element for multiplicative group of order $n$ - feasible?

texts:
Given a multiplicative group of order $n$, how hard is it to find a generator element (such that all other elements can be expressed as powers of that generator)?

What would be the complexity?


texts: What is the signature scheme with the fastest batch verification protocol for multiple signers?

texts:
I'm looking for a scheme where signing may be costly (slow) but batch verification with different signers is the fastest possible.

Modified ECDSA allows batch verification for different signers with a 4X speedup [1].

Is there any signature scheme than can do better?

[1] Fast Batch Verification of Multiple Signatures. Jung Hee Cheon and Jeong Hyun Yi


texts:
Let's assume I want to send a secret message to $N$ recipients in an asymmetric way.

My message could be encrypted with $N$ different public keys $p_i$ one after another and send to each user individually. In practice only a symmetric key $k$ is sent in an asymmetric way I guess, but that's not the point.

Even direct symmetric encryption comes into mind where the key $k$ is encrypted with each $p_i$ once and attached to message body afterwards. Of course the message length grows with rising $N$.

So I wonder if there is an encryption function having $N$ public keys as input.
This fixed length encrypted message should be decrypted by corresponding private keys only. Is this possible?

By the way: Is this concept similar to TV channel encryption?


texts: Different kind of PGP keys or IDs, how to interpret them?

texts:
When people say "Here's my PGP key", they tend to come up with all sorts of different stuff.

Sometimes they provide an 8-digit hexadecimal number, which seems to be a key ID (although I'm not sure).

I've also seen cases where people provide a 16-digit hex number, or even a 40-digit number (printed as 10 fields of 4 hex digits).

I've also seen cases where people send a file, containing the usual stuff:

-----public key-----
....
(whole lot of base64 encoded data)
....

I can deal with the latter, but I have no idea how to obtain the key from the other formats. How do I go about this?


texts: How to associate a post-quantum public key with a pre-quantum one in blockchains?

texts: As a layperson, I'm curious if a cryptocurrency could fork to a quantum-resistant algorithm without people losing access to their wallets. Is it possible to generate a quantum-resistant public key from the wallet's private key (that was used before the fork)?


texts: I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, and typically only discuss SIS and LWE. According to this post, Are LPN and LWE problems equivalent?, LWE is a generalization of LPN. From what I understand, SVP (derived from SIS), and LWE are common lattice trapdoors. Is LPN not an important lattice trapdoor worth discussing? If it isn't, why is that the case?


texts: Encrypt HDD with keyfile and password and allow backing up the keyfile with secret sharing

texts:
I want to:

Encrypt my whole HDD with a keyfile and a password (meaning that both are required to decrypt it),
Be able to back up pieces of the keyfile in several distant locations using Secret Sharing,
Be able to change the password often and easily.

Notes:

The keyfile is made of 4096 random bits and is done using dd if=/dev/urandom /keys/keyfile bs=1024 count=4,
The password is approximately 20 characters long,

To make things clear, I'll state the intended meaning of a few words:

keyfile – the randomly generated file
password – the text asked to the user and never stored in a file
key – the data used to decrypt the masterkey
masterkey – the data used to encrypt / decrypt the drive

Thoughts:

To allow “3.”, I use cryptsetup since it uses a masterkey that's encrypted with your key so I can change my key without having to rencrypt everything. I could use dm-crypt directly but it'd be much harder and would only save the space occupied by the luks headers. And I already have enough space so I don't think it's worth the trouble.
To allow “1.”, I could encrypt the keyfile with the password and use the keyfile as key but then,

If I backed the encrypted version of the keyfile, I'd have to update all backups every time I changed the password,
If I backed the non-encrypted version of the keyfile, I'd allow to bypass the password by recovering the backup.

So instead, I chose to combine the keyfile and the password.

Combination of keyfile and password into key:

I use a bitwise XOR to compute the key from the keyfile and the password. I start at the left and when one of then is empty, I just output the rest of the other one. See my C source file at GitHub.

The other option I thought of was concatenating them. But I didn't like the idea of my key having a recognizable pattern: Random data followed by text.

I therefore used the XOR because it preserves the randomness: for a given password, the distribution of a uniform distribution XORed with that password is still the uniform distribution.

Current state:

I have something that should work and if there are bugs, I probably will be able to fix them.

Questions:

Is /dev/urandom fine for my use-case or should I use /dev/random?
Some people told me that I should use a key derivation function because otherwise, the effect of the password isn't spread. But do I need the effect of the password to be spread? The way I see it, cryptsetup will already use a key derivation function on my key to increase computation time and try to spread the effect of each bit.

Feel free to criticize (constructively) any decision or assumptions I've made (for that project).


texts:
In Bellovin's ESP Attack,
it is stated that:

  If $L_A$, $L_B$ are using UDP, attack is easier:

  Wait till session ends
  Allocate $L_B$'s UDP port to $X_B$
  Replay all packets

So, how does attacker know the UDP port of legitimate user $L$? Isn't it encrypted (because the UDP header encrypted)? How can the attacker obtain it?

Also, if the attacker knows the UDP port number of legitimate user, why should he wait till the end of the session? He can sniff the packets and change the UDP port number. Then he can receive the packages in another port during the session. Is my assumption wrong?


texts: Is frequency analysis a viable attack on non-text data encoded by substitution?

texts: Is frequency analysis a viable attack on non-text data encoded by substitution (eg image and audio formats encoded with a substitution cipher)?


texts: How could Fully Homomorphic Encryption support power operations?

texts:
Fully Homomorphic Encryption (FHE) enables arbitrary functions computed on encrypted data, because it supports both addition and multiplication. But I wonder if FHE supports power operations.
For example:

$$C \leftarrow E(m)$$

$$y \leftarrow 2^C$$

$$2^m \leftarrow D(y)$$

I went over some FHE schemes like DGHV, it seems they don't support that.


texts: Dieharder How can I make my input file suitable for Dieharder?

texts:
I created my random numbers and I saved them into a txt file. My input file includes just 0 and 1. Here is the link of my file
And I of course read some answer before asking that question but I could not understand how can I create an input file for diehard. Do diehard have some prepared comment for converting our input file for itself or we should do it by hand? If we should do it how? I see too many parameters like generator see type count numbit ...
Could you please help me?

Update: I actually answered this question but I have some troubles related my account so the answer is just lost so I am writing again

Many thanks for your answe rI think it finally worked with that

just to be sure: what is d? when I looked other example I sometimes saw b instead of d

I have just 0 and 1 so numbit should be 1 I guess, right?

and you wrote some numbers and they are actually random numbers right? (In my case it is jut 0 and 1 instead of 3129711816 85411969 2545911541)

And I want to test how much my numbers are random with this file and this code script right?

Also When I tried without changing my file as a header file, it worked with this code script: dieharder -a-f your-file.txt and what does thos script mean? OK it worked but I couldnt change my file like header file and I dont know what it means

Update-------------------------------------------------------------
Hello, I still have some troubles regarding matching of accounts so I am updating here
1)Happy Christtmas to you too!
I have not a bin file! Why do you think that. I am trying to produce quantum random numbes and my numbers will be either 1 or 0 and after producing them, I save it a txt file! WHat is the problem with txt file. I really dont understand your point. And studyong with diehard how many numbers should I have at least? 2000000 is not enough??
What are the other techniques
2)And can you please explain my questions, if you have seen them like what is d or is my header file correct?...
3)How can I convert my txt file as a binary file???
4)What is the other techniques for testing how much my numbers are random? Can NIST be ok?
5)For instance I used this line for converting bin file perl -ne 'print pack("B32", $_)' < instructions.txt > instructions.bin is that ok? And I used 10000000 data and I convert it as binary file and it was extremely fast. I think it should has been slow?
Important note: I am using dieharder 3.31.1 version


texts: How to compute two EC point multiplication?

texts:
I would like to know how to compute multiplication of two valid EC points over a curve E with generator G.

i.e. Given only P and Q points then how to compute R = P * Q

where $P = p G$, $Q = q G$ and $R = (p \cdot q)G$.


texts: Is it possible to weaken a bitcoin private key by 'using' it elsewhere?

texts:
What are the increased possibilities (if any) of being able to crack a private key given the following:

The associated bitcoin (ECDSA Secp256k1-based) public key is known.
The private key has been used to generate a public key from a different ECDSA curve and that public key is also known.
It is known that the two public keys are derived from the same private key.
It is known which ECDSA curves were used to generate the public keys.
It is known which ECDSA curve was used to generate which public key.


texts:
Cryptographic procedures seem to almost exclusively use discrete logarithms rather than continuous logarithms. Hence, I assume there are good and sound reasons for this.

In essence, answers provided here:
Why is NON DISCRETE logarithm problem not hard as the DISCRETE logarithm problem (so computationally hard)?
 state that continuous logarithms, thus, non-discrete logarithms can be computationally fast, while for discrete logarithms no such algorithm is known.

Furthermore, continuous logs can pose the problem of mathematical precision in terms of rounding errors.

For any non-discrete logarithm problem such as:

$$v = \log_{b}e$$

solving for either an unknown base $b$ or an unknown exponent $e$ is trivial when $v$ is known.

So my question is, not considering rounding issues, for now, what about solving for $v$ in the equation above, however when both the base and exponent are unknown, with the base $b$ being prime and $e$ being a random integer greater than 1.


texts: Does a cryptographic oracle have to be a server?

texts:
I've been told that oracles are always servers and that oracle attacks are always online, but I'm not convinced that's true. However, I have limited understanding of this topic since I'm still learning and the book I just read didn't discuss it at all. The definitions I've seen of the term don't specify whether oracle attacks are always online/involve servers either.

Is an oracle always a server?
Can padding oracle attacks happen offline (e.g. an encryption tool)?
Can partitioning oracle attacks happen offline (e.g. an encryption tool)?

Please explain things in layman's terms.


texts: Security analysis of this one time password based scheme for copy protection

texts:
Imagine such protocol.
Client and server initially share secret K[0].

When client wants to contact server she sends server K[0] and her ID.
Server accepts request, and generated new random K[1] and sends it to client which should use this in next communication.
Again, if client wants to authenticate with server now, she sends K[1]. Server accepts it if correct, and sends here K[2] to use next time and so on.

My first question is: Is there some name to this protocol in the literature? (Where security of this protocol has been studied?).

I want to use it for detecting if someone copied software of my client.

For me this scheme works most of the time: because if someone copies the client software it means the copy of the original software, will send say K[n] th password to server who will generate next password for client K[n+1]. But this way original client will go out of synchronization with the server because she will use old K[n] to authenticate and we will detect this - and achieve our goal.

The only attack I can see on this protocol if man in the middle just forwards clients messages to server and servers response to client.
Someone can present security analysis of this scheme?


texts: Where can I find official test vectors for NIST SP 800-56C r1 Single Step KDF

texts:
NIST 800-56Cr1 describes a single and two (extract-expand) step KDF designed for use in key agreement routines. NIST declares that HKDF (RFC5869) is a version of the two-step variation so test vectors can be found in the RFC. However I am not able to find test vectors for the former, one-step variation.

There are some for KBKDF (aka SP 800-108) in the Cryptographic Algorithm Validation Program, but not for 800-56C specifically. Can someone point me to the official or other test vectors?


texts: Conditioning Component in Entropy Source

texts:
Given a sample of random bytes, how to determine if Entropy Source (source of random bytes) includes a Conditioning Component or not, with respect to NIST SP 800-90 B)?

Thanks


texts: Safety of using GPG's libgcrypt prime generation for generating ephemeral Diffie-Hellman primes?

texts:
My company wants to generate new primes for every Diffie-Hellman key exchange.  We are thinking of using the prime generation scheme in GPG’s libgcrypt library.

The code documentation says that the scheme that libgcrypt uses is based on a paper from Crypto 97.  It is entitled, ”A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup”  and is by Lim and Lee.

Is this Prime Generation scheme by Lim and Lee still considered secure?  Is the libgcrypt code the only implementation of this scheme?


texts: What is the efficiency of the new Crown Sterling semiprime factoring method?

texts:
In their press release a company called Crown Sterling describes they are working a paper that

  includes four different geometric and arithmetic methods for public key (semiprime) factorization and one of the methods titled, “The Reciprocal Factoring Method” includes an analysis of reciprocal values of public keys and their embedded private keys (prime factors) found within their period decimal extensions.

According to the CEO's Instagram, the factoring method is quite simple: search for the primes in the decimal expansion of the reciprocal of the semi prime. It doesn't hold true for all primes, and I get that its not even remotely efficient enough, but while the controversy is ongoing, it would be helpful to know just how inefficient their method is.


texts: How to understand RSA Proofs of correctness at Wikipedia

texts:
From Wikipedia(https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29#Proofs_of_correctness):

$m^{ed}$ ≡ $m$ $\pmod{q}$
$m^{ed}$ ≡ $m$ $\pmod{p}$
 then $m^{ed}$ ≡ $m$ $\pmod{pq}$

Question:
if $m^{ed}$ ≡ $m$ $\pmod{q}$,then $q$|$m^{ed}$- $m$
if $m^{ed}$ ≡ $m$ $\pmod{p}$,then $p$|$m^{ed}$- $m$
that is to say, $m^{ed}$- $m$ is the common multiple of both $p$ and $q$

At this time, if there is $lcm(p,q)=pq$, then $m^{ed}$ ≡ $m$ $\pmod{pq}$.
However,  I am not sure $lcm(p,q)=pq$ holds true or not, so how can I prove $m^{ed}$ ≡ $m$ $\pmod{pq}$?


texts: What are the odds of collisions for a hash function with 256-bit output?

texts:
There are some related questions on the net but I did not understand their solutions.

I am reading in a textbook about methods of finding a collision. It states  to consider a collision for a hash function with a 256-bit output size and writes if we pick random inputs and compute the hash values, that we'll find a collision with high probability and if we choose just $2^{130}$ + 1 inputs, it turns out that there is a 99.8% chance at least two inputs will collide. It also says we can find a collision by looking at roughly the square root of the number of possible output results.

Questions:

What is the formula used to calculate that if we choose $2^{130}$ + 1 input at least 2 inputs will collide with a 99.8% probability?

From my research it looks like this is related to the "birthday attack" problem, where you calculate first the probability that the hash inputs DO NOT collide and subtract this off from 1. Whenever I tried to plug and chug using the formulas I found online I wasn't getting the results the book stated.

Edit: I tried using the formula P(A) = 1 - $\frac{k!}{(k-n)!k^{n}}$ and obtained
99.99...%. I do not know how the authors obtained the percentage 99.8%. Can someone please state the explicit equation used, so I can see how the book gets the 99.8% probability of collisions with $2^{130}$ + 1  randomly chosen inputs? Where does the +1 come from?
How is the square root function related to this? If I take square root of 256, I get 16. What does this mean in the context of collisions?
The size of the output is 256 bits. Does this mean the total number of possible outputs is $2^{256}$?
Does the pigeonhole principle apply to this? You are taking an infinite amount of inputs and mapping them to a finite amount of outputs.


texts: Is this a good Pseudo-Random Number Generator?

texts:
I discovered what appears to be a good quality pseudorandom number generator, but I have not subjected it to any statistical tests beyond bit frequency, bit pair frequency, and least-significant bit frequency tests. It generates a block of bytes by evolving deterministically, starting with a seed state. I'm new to Stack Exchange, so please bear with me.
Here is the process (test example):
start with a 32-byte sequence (256 bits) and an integer variable k, and for each byte X(i),

$s = 7 - (X[i+1]+X[i+2]) \bmod 15$
$X[i] = ((X[i] + k) * 2^s) \bmod 255$
$k = k + X(i)$

and I implemented this process in C as follows:
    #define CYCLES 1 // full cycles per byte of the seed size per evolution
    unsigned int i, j;
    unsigned char a, k;
    int s;
    for (i = 0; i < 32*CYCLES; i++) {
        a = X[i%32]+k;
        s = 7-(X[(i+1)%32]+X[(i+2)%32])%15;
        for (j = 0; j < abs(s); j++) {
            if (s<0) {
                a = ((a&1)==1)?((a>>1)+128):(a>>1);
            }
            else {
                a = ((a&128)==128)?((a<<1)+1):(a<<1);
            }
        }
        X[i%32] = a;
        k += a;
    }

The C implementation of modular multiplication by powers of uses bitwise operations and differs in only one way from an algebraic method: when a = 255, the output is always 255. This is essentially a rotation of the byte abs(s) times to the left when the sign is positive, and the right when it is negative.
If I initialize the array X with a seed value such as "ABCDEFGHIJKLMNOPQRSTUVWXYZ012345" and evolve it 32 times, then map out the resulting bits or do basic tests for randomness, it appears to be very similar to true randomness. Am I missing something, or is this a good PRN generator?


texts: Known-plaintext attack against E0 with 2745 bits per frame instead of 24

texts:
In the paper The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption, an attack against the E0 cipher is described which can break it efficiently in a known-plaintext attack:

  Our best attack finds the original encryption key for two-level E0 using the first 24 bits of 223.8 frames and with 238 computations. This is clearly the fastest and only practical known-plaintext attack on Bluetooth encryption compared with all existing attacks.

Interestingly, the attack requires the first 24 bits of a number of frames. Each frame is 2745 bits in size. They mention that predictable redundancy in the Bluetooth frame may make it possible to turn this into a ciphertext-only attack. If we assume that it's not the case but additionally allow the attacker to access the entire frame rather than the first 24 bits, how efficient does the attack become? How many fewer frames will an attacker need to recover the initial 128-bit key, or are all bits past the first 24 unnecessary?


texts: What are some good examples of modifying crypto where flaws are not really obvious?

texts:
I run into some developers from time to time who sometimes try to modify crypto which I end up saying along the lines of "Don't modify crypto." Usually, the question I get is - "OK, tell me why is this bad? How can this be broken?"

My rule of thumb is usually that cryptographic primitives are supposed to be used they way they are told. A slight modification in those primitives or assumptions can break cryptography in a way that cannot be foreseen. However, I am not that really good with spotting flaws on spot. Plus, finding flaws every time I face such modifications is time consuming. I generally like to explain this to people using examples. How can I explain people that they should not modify cryptographic primitives?


texts: Is there a scheme where two cipher texts can be proven to have the same (unencrypted) content?

texts:
Is there a scheme where two ciphertexts (encrypted with different keys) can be proven to have the same (plaintext) content without disclosing the plaintext or any private keys?  I assume that the public keys would need to be known.

This is for the purpose of detecting duplicated content on a server, without knowing the content.

This is probably impossible, but reading about homomorphic encryption leads me to think that it might be possible.


texts: PBKDF2 for login key, scrypt for encryption key

texts:
I need to derive two keys from a single password client side.
One for in-browser login, the other for encryption.

Is the following secure ?

login key      = pbkdf2(password, salt1, lowN)
encryption key = scrypt(password, salt2, highN)

Explanation:

Server shouldn't know plain password
salt1 is retrieved from server upon login
User logs in using login key, download data + salt2, then decrypt it using encryption key client side.
I would love to just use scrypt (stronger), but the only vetted key derivation JS library I found is pbkdf2 by SJCL. Plus I need user to be able to login to website from mobile devices.


texts: A proof-of-work random number generation system for Pokémon

texts: (The original question that was here was considered too confusing, unclear, and rambling. You can still view it in the edit history, but the content is no longer useful by itself, and cannot be reasonably reconstructed into a question suitable for this site. The question object is still here by decision of a moderator, as a placeholder to preserve any reputation gained by the answerers of this question while it was still active, as well as to preserve the original question content in case any new questions are built upon this one.)


texts: Elgamal with secret key equal to zero possible?

texts:
From various sources (e.g. this paper, page 3), the key generation algorithm of Elgamal samples the secret key $x$ from $\mathbb{Z}_q$, which is identifiable to $\{0, 1, 2, \dots, q-1\}$.

My question is: what happens when the sampled $x$ is, say, zero? Indeed, in this case, the public ley $h$ is equal to 1, and encrypting plaintext $m$ with randomness $r$ yields $(g^r, m)$. This seems to me like a serious issue. The same happens with $x = 1$. In this case $h = g$, it is easy to notice that $h$ is equal to $g$ and deduce that the secret key is $1$.

Of course,this "methodology" does not extend to any value of $x$ (testing whether $g^x$ is equal to the public key), since this is pretty much a brute force attack, by assumption computationally infeasible. I also understand why the scheme can be proven secure, though: because $q$ is so large that the case $x = 0$ or $x = 1$ happens with a negligible probability. Yet, in practice, it can happen... Do implementations take that into account?


texts: Is there any difference in adding the plain text and key vs using xor instead(apart from the performance improvements)?


texts: Why are co-factors 4 and 8 so popular when co-factor is more than one?

texts:
For elliptic curve cryptography, I seem to keep coming across curves with either co-factors of 4 or 8 whenever it is a non-prime order group.

Is this a co-incidence? Have we studied ECC for curves which produce cofactor = 3 for example?


texts: Unique decoding Radius in Reed Solomon Codes

texts:
In one of the coding theory books I read the unique decoding radius for Reed Solomon codes is $\frac{1-\rho}{2}$. Precisely, if the relative distance be less than these amount so the receiver is able to reconstruct the noisy received code-word uniquely. While for bigger amount of relative distance there are other code-words that are closer to the received code-word instead of the original code-word.

How this bound is calculated?


texts: How would you encrypt-then-MAC when using pen-and-paper and a Caesar cipher?

texts:
I'll probably get shot for asking this, but I've got some kids (aged 8-10) in my neighbourhood that I've been showing/teaching the simple pen-and-paper Caesar cipher and they're successfully playing with it for more than a week now.

Silly me thought it would be great to now show them the concept of message authentication and how it practically works; especially that it can be used to show if the message has been modified by someone along the way or not. So the plan was set and the promise made as it suddenly dawned upon me that I never used anything else but computational power to calculate (H)MACs… and that's not exactly a pen-and-paper solution for the kids.

Now, the good thing is that they don't need a national-security-level encryption, which means I could use any simple (read: improvised) hashing method as long as it works using pen-and-paper. But such simple hashes are obviously hard to find. So currently, I am thinking of simply replacing the usual hashing with an addition-based checksum thing. That could work, but I'm not so sure that that's really the best option.

Keeping in mind that I need to explain MAC to kids aged 8-10 so they can practically do it themselves using nothing but pen-and-paper, do you have a better idea? How would you encrypt-then-MAC when using pen-and-paper and a Caesar cipher to practically show them a working message authentication?


texts: Is a strong block cipher usable as a strong sponge function?

texts:
From the literature, it looks like the security proofs of sponge functions depend on how well they approximate a random permutation, Since a block cipher also ideally behaves like a random permutation does that mean strong block ciphers make for strong sponge functions?

As in, can I expect:

extern char *input,*output;
extern int input_length,output_length;

char block[16] = {0};
char key[16] = {0};
for(i = 0; i < input_length; i++) {
    AES128_ecrypt(key,block,block);
    block[0] ^= input[i]
}
for (i = 0; i < output_length; i++) {
    AES128_encrypt(key,block,block);
    output[i] = block[0];
}

to be a cryptographically strong sponge hash of rate 8 bits and capacity 120 bits and hence be strong against $2^{60}$ attacks?