texts:
I am trying to design a file exchange protocol for learning purposes, inspired by PGP, but fixing some of its shortcomings.

Assuming the machine where the creation and decryption of the file happens are secure, the threat is a passive (reading file) or active (manipulating file) attacker on the line.

These attributes must be granted:

only decryptable by the intended receiver
receiver can verify sender identity
any manipulation to the data will be noticed by the receiver

So we need encryption, authentication, and a signature.
After the study of this paper and several other, more basic principles, my protocol draft currently looks like this:

the masterkey is random and used to derive HMAC and symmetric cypher key.
IV is random and included inside the MAC.
algorithm agility metadata is added inside the public key encrypted part to denote what hash is used for signing and MAC, and before the IV to transmit the symmetric cipher algorithm and mode.
the recipient is identified by public key fingerprint.

What are the dangers or flaws I did not think of in this protocol?


texts: Zero-Knowledge Proof of a Turing Machine

texts:
Quesstion:
Suppose Peggy claims to have a Turing Machine (TM) such that when the tape starts with I the machine will halt with tape O for one or more (I, O) pairs.
Peggy would like to prove to Victor that she know the TM, but would like to convince him via a Zero-Knowledge Proof (ZKP).
Is there an algorithm $\Pi$ that Peggy and Victor can run that will accomplish this?  If so what is it?
Example:
Let's say that I write a function $f(x)$ in some programming language.  Now I would like to prove to you that $\forall x f(x) = 2 x^2-x+5$ but I don't want to disclose any information about the source code.  (I know that this is a silly example but you could imagine that $f(x)$ is a much more complicated function)
Ideas:
Maybe there is a way to convert this into another problem that we have a algorithm to proof in zero-knowledge
Clarifications:
Let's start with an application for an example.
Peggy is a student and Victor is a teacher.  Victor assigns a homework in which Peggy is supposed to design a TM to compute some function, $f(x)$.  Peggy designs a very elegant solution and no longer wants to disclose her TM to Victor. (Maybe Peggy is afraid that Victor will steal her idea)  Instead she wants to convince him that she did the assignment via a ZKP so she can get credit.
Another example is proprietary software.  A company wants to convince its users that their software does what the users expects it to so.   One popular solution is currently to release the software (e.g. open-source), but this allows anyone to easily steal the software.  An alternate could be to provide a ZKP that the software satisfies certain properties.
What information do Peggy and Victor have?

Peggy and Victor know all the (I,O) pairs.
Peggy knows some TM such that $\forall i \forall o ((i \in {\bf I} \wedge o \in {\bf O}) \rightarrow {\bf TM}(i) = o)$
Algorithm $\Pi$ should ideally run in polynomial time of the runtime of the TM
Ideally Victor should not learn the number of states of the TM or the number of steps needed to compute the function, but if there is an algorithm that works except for these properties that would still be great.

Learning some upper bound of the number of states or runtime is fine though

If needed Peggy and Victor have access to a Random Oracle


texts: Does a conditional statement depending on a round number introduce timing attack problems?

texts:
In a cryptographic implementation I’m playing with, there’s a round function which includes a conditional if statement.

Stripping the superfluous stuff, the C sourcecode looks like this:

void f(uint32_t *state) {
    …
    for(round = 0; round < 12; round++) {
        // functions working on state
        …
        if((round & 3) == 0) {
           // additional functions working on state
            …
        }
        …
    }
    …
}

Trying to check if this might introduce timing attack problems, I looked at cryptocoding.net which states:

  If a conditional branching (if, switch, while, for) depends on secret data then the code executed as well as its execution time depend on the secret data as well.

This seems to hint at the fact that, as long as the if function does not depend on the state itself (which is meant to be handled as secret), there should not be a problem because if in this case depends on the round number and not the secret state.

Is my interpretetion indeed correct, or does that if represent a potential problem regarding to timing attacks? In case my interpretetion is wrong and it represents a timing attack problem, would unrolling the loop (manually by rewriting the code) be a valid way to mitigate it?


texts: Getting the same two hash values for carved files I found

texts: I am doing an independent study class for computer forensics, I have to carve the images I've been given. After using scalpel I get a .wav file and .asf file both files play the same songs, and they generate the same md5 hash values. Is this because they are the same file just with .wav and .asf at the end or I am possibly doing something wrong?


texts: Is my method of identifying remote ZMQ clients secure?

texts:
ZMQ provides a CURVE based authorization / encryption system based on certs/keys.  After endpoints are authenticated to the server, they can send an "identity" with each request.  Unfortunately they set this identity themselves, and it's not based on their key.

I don't want to trust that the clients are who they say they are.  So in addition to the ZMQ CURVE security I have the clients hash (sha256) a password they have (unrelated to the ZMQ auth), and send it with each message.  The message itself is encrypted by the ZMQ security.  For each message, the server takes the hash, compares it to what's in the database for the station, and allows the message if the hashes match.

Is this a secure way to verify clients are who they say they are, given it's all encrypted by another (presumed secure) system?


texts:
Normally, when decrypting messages, you need to check if the message is authentic and integral (aka, never decrypt before checking the MAC).

With ECIES, this seems to be done internally. Is it necessary to include a MAC on your messages you encrypt when using ECIES?


texts: Key derivation for AES-Encryption key and HMAC

texts:
Okay so I have two options for how I would derive two keys for AES encryption and HMAC they are as follows:

Run BCrypt on a users passphrase and then use the bouncy castle implementation of HKDF in java to extend the key from 31-bytes to 64-bytes before then splitting the result into two 32-byte keys.
Run Bcrypt twice on a users passphrase with a different salt and then use the bouncy castle implementation of HKDF in java to extend both keys from 31-bytes to 32-bytes.

My question is which way is better? (more secure)

Note: If you do have a answer please leave your reasoning in a way that is easy to understand.


texts:
I was thinking about creating a proof of concept for the following type of website login system.

Instead of passwords being used, on account creation, a public GnuPG key is uploaded to the server, and that serves as the main form of authentication for a users account. To login, the user would give their username. The login app would get the usernames public key, encrypt a random string with their public key, and the user would have to decrypt that downloaded file, and used the decrypted string as the password.

Does there seem to be any flaws in that system? If the user is able to keep their key secret, I don't see why this type of system wouldn't be feasible.

What do you think?


texts: CSPRNG in JavaScript using Audio and Video

texts:
I ported GnuPG to Javascript using Emscripten (not released yet).
Now I need a good replacement for /dev/random//dev/urandom.
New browsers support window.crypto.getRandomValues() but for older browsers I need something else.
I was thinking about recording some audio using HTML5 and calculating the sha 512-bit digest.
Then splitting this digest into two halfs and using them for AES 256-bit encryption (256-bit IV and 256-bit key) of a photo taken also with HTML5.

Is it safe to use this encrypted image as a replacement of /dev/(u)random?
Which mode should I use for AES encryption?


texts:
I have a use case, the IoT system sending a signed file to the data center and I have an internal CA to read the corresponding public key to verify the signature on the signed file.

I am not sure how the flow work functions if I am sending a signed file from the data center to IoT. Does the CA help to sign the files? And I don't want to read the private key out from a HSM to sign the file--isn't that correct?

Can someone please help with how I could send the signed files from the client to server and server to the client?

To make it a bit more complex, I want to sign and encrypt as well.
My requirement is to store the private key on a HSM (server-side) on TPM (IoT).


texts: Rationale for verification with cofactor $2^c$ in EdDSA?

texts:
In EdDSA for more curves, it's described two options of signature verification

Verification, which checks $2^c\,S\,B\,=\,2^c\,R+2^c\,H(\underline R,\underline A,M)\,A$
Cofactorless verification, which checks $S\,B\,=\,R+H(\underline R,\underline A,M)\,A$

Cofactorless verification is more stringent: "any alleged signature that passes cofactorless verification will also pass verification", but "a signer using a secret key outside the normal signing procedure can create strings that pass verification without passing cofactorless verification".
So, what's the rationale for the first kind of verification, with cofactor $2^c$? If somewhat it's faster/simpler, why?

Update: after looking at this answer and it's references, I wonder if the only reason Verification¹ is defined is so that it holds the following
Proposition: If a set of signatures passed batch verification, then each signature passes Verification¹ with cryptographic certainty (including if signers are intentionally messing up or if adversaries modify signatures).
Is this proposition true? What's a proof? Why would not it hold if Verification was defined as Cofactorless verification?
Is there any other reason for Verification with cofactor? Like, a Fast Single-Signature Verification as in section 5 of Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang, High-Speed High-Security Signatures, in proceedings of CHES 2011)?

¹ Verification as defined above, that is with cofactor $2^c$.


texts: Why is RSA secure if I can solve the equations for it using a math solver?

texts:
To factorize N = p * q with p < q e (p-2) mod 9 = 0, there are a set of equations. These equations can be put into any popular math solver, in order to gain access to the primes p and q. For instance, the prime components of the public key N = 209 can be solved as follows:

[(h+1)^2]*[(2*h+2)^2/2-1] = X*(209-4-2*n+2*(p-2)),(h+1)/3=(k+1)/6 ,p^2+n*p=209,
                            h+1+k+1=(209-4-2*n+2*(p-2)),h,X,n,k

->

h = (2 (-209 + 99 p + 2 p^2))/(3 p)

[(h+1)^2]*[(2*h+2)^2/2-1] = X*(209-4-2*n),(h+1)/3=(k+1)/6 ,p^2+n*p=209,
                            h+1+k+1=(209-4-2*n),h,X,n,k

->

h=(2 (-209 + 101 p + p^2))/(3 p)

(2 (-209 + 99 p + 2 p^2))/(3 p)-(2 (-209 + 101 p + p^2))/(3 p)=6

->

p=11

This shows that p = 11. By simple division, it can be determined that q = 19.

It seems to me as if this approach is somewhat obvious, and I'd like to know how RSA is still considered secure if I can do these calculations in a math solver?


texts: How does a receiver treat X.509 self-certificate with unknown the Signature Algorithm ID?

texts:
As I know X.509 self-certificate is a mechanism that the host generates public and private keys, the public key will insert to a certification and the private key will be used to sign the certification. The receiver will verify the certificate by using the public key with certification.

In case if the receiver does not have the algorithm that used to sign the certification, how the receiver can verify the certification?

Does X.509 has default algorithm to sign the certification?


texts: How is the SPI determined/negotiated in phase 2 of IKE (v1)?

texts:
While I am aware that the SPI (along with destination IP and protocol) is used to uniquely identify an incoming SA on a peer, for the life of me I am not able to understand how that particular SPI value is determined and agreed upon by both peers during IKE phase 2 message exchanges, for both the incoming and outgoing SA that are established on each of them. I have come across sources stating the below:

  The SPI is a 32-bit number that is chosen by the initiator to uniquely identify the outgoing IPSec SA that is generated as a
  result of this negotiation in its database of security associations.
  The responder, upon seeing the SPI, makes sure that it is not the
  same as one of the SPIs it is using and starts using it for its
  incoming IPSec SA. It also proposes an SPI for its outgoing (and the initiator's incoming) SA, which the initiator agrees to after
  checking.

The above scheme seems more like a trial and error than a negotiation. Logically, I would expect the responder to chose a value for the SPI that is not currently in use for its incoming SA, and send that over to the initiator to record in its SAD and encode the same in all future AH/ESP payloads it sends to the responder over this SA. My questions are as below:

Is the above description actually how it takes place?
If yes, what happens in case the responder receiving the SPI from the initiator finds out that the SPI value is already in use?


texts: Efficient protocols for set membership proofs with private sets

texts:
I found the paper on Efficient Protocols for Set Membership and Range Proofs in which
efficient protocols for the following problem are discussed:

Given a commitment $C_v$ to a value $v$ we want show with a zero knowledge proof that $v$ is in a set $\Phi$.
Only $C_v$, and $\Phi$ is publicly known in this scenario

However, I wondered if there are also efficient protocols for the following problem:

Given a commitment $C_v$ to a value $v$ and a signature $\sigma_\Phi$ on a set $\Phi$.
Is it possible to efficiently show with a zero knowledge proof that $v$ is in the set $\Phi$ if only $C_v$ and $\sigma_\Phi$ are publicly known?

I read the very similar question Constructing set membership proof for private set. However, the difference there is that the element in question is publicly known and also no efficiency is considered.

Edit: Thank you Mikero, you were right. I did not consider the possibility that a signature might include a copy of the plain message :)

My intention is to do the following:

Suppose there are three parties: A prover $\mathcal{P}$, a verifyer $\mathcal{V}$ and a third-party $\mathcal{T}$.

We have a set $\Phi$ with signature $\sigma_\Phi$ from $\mathcal{T}$.
$\mathcal{P}$ wants to efficiently prove to $\mathcal{V}$ that the commitment $C_v$ belongs to a value $v$ in the set $\Phi$, without $\mathcal{V}$ learning either $\Phi$ or $v$.

Basically $\mathcal{P}$ wants to prove that a value $v$ belongs to a set $\Phi$ from $\mathcal{T}$ without revealing the value or the set.


texts: Is it possible to track down copies of WW2-era codebooks?

texts: I've got an academic curiosity regarding some of the old Japanese naval codes used during World War II specifically.  I'm wondering if any of the codebooks from this era have been made available, or if they are still protected materials?


texts: Is there an encryption method where the order of decryption is irrelevant to the order of encryption?

texts:
With most encryption methods, if a message is encrypted first using key $k_1$ and then using $k_2$, to decrypt it you have to use first $k_2$ and then $k_1$.

I was wondering if there are any encryption methods that can be decrypted using the keys in any order. For example, if a message is encrypted using the keys $k_1$, $k_2$ and $k_3$, in this order, then it could be decrypted in the order of $k_2$, $k_3$, $k_1$ or in any other order, as long as all 3 keys are used.

Simple XORing the keys and the message is possible (where the key space is the same as the message space) but if multiple messages are encrypted, it is not secure.

So my question is: Is there an encryption method where the order of decryption is irrelevant to encryption, but which is also secure with multiple messages? The size of the keys doesn't matter.


texts: Does cryptographically-secure pseudo random generators require a secure seed?

texts:
For any cryptographically-secure pseudo random generators, do we need a secure random seed for those?
If the seed is predictable, then everything is broken due to the deterministic propetry of the algorithms.


texts: Should RSA primes p and q differ in length by "a few digits"?

texts:
When generating RSA keys in the original RSA paper it is stated:

  to gain additional protection against sophisticated factoring algorithms, p and q should differ in length by a few digits

Why is this? How many is "a few digits"? And how important is this?


texts: Strong pseudo random permutation implies CCA-security

texts:
Let $F$ be a strong pseudo random permutation and define a fixed-length encryption scheme $(\operatorname{Enc,Dec})$ as follows:

On input $m \in \{0,1\}^{\frac{n}{2}}$ and key $k\in \{0,1\}^{n}$, algorithm $\operatorname{Enc}$ chooses a uniform string $r \in \{0,1\}^{\frac{n}{2}}$ of length $r/2$ and computes $c:=\operatorname{F}(k,r\mathbin\|m)$. Prove that this scheme is $\text{CCA}$-secure.

How can I show that strong Pseudorandom permutation implies $\text{CCA}$ security? I don't know how to do the reduction.


texts: For RSA, is there a specified size range for $p$ and $q$ when calculating $N$?

texts: Is there a specified size range for $p$ and $q$ when calculating $N$? For example, what size would $p$ and $q$ be when $N$ is 1024 bits?


texts: Trying to attack specific encryption scheme

texts:
Let's consider 128-bit cipher. Now let's consider example keys $k_1$ to $k_{128}$:
$k_1$: 10
$k_2$: 1100
$k_3$: 11110000
...
In general every key $k_n$ can be some binary number which is consist of $n$ zeros and $n$ ones. This keys are mapping some encryption scheme. If $k_1$ is 10 it means that all least significant bits in encrypted numbers from $0$ to $2^{127}-1$ will be $1$ and all least significant bits in encrypted numbers from $2^{127}$ to $2^{128}$ will be $0$. And if $k_2$ is 0101 it means that all second least significant bits in encrypted numbers from $0$ to $2^{126}-1$ will be $0$, all second least significant bits in encrypted numbers from $2^{126}$ to $2^{127}-1$ will be $1$, all second least significant bits in encrypted numbers from $2^{127}$ to $2^{127}+2^{126}-1$ will be $0$ and all second least significant bits in encrypted numbers from $2^{127}+2^{126}-1$ to $2^{128}-1$ will be $1$. So the keys define how batch of the bits will be encrypted.
Not every state is allowed. To define all encryption secheme in one round we need $508$-bit main key and use it in specific algorithm, which is separate topic. It is not enough to determine all schemes as above. So we can define only some of states.
This is how works one round of encryption in my algorithm. I thougt about at least $10$ round of such encryption. To guess $k_1$ we need to geuss only one bit of the main key. To guess $k_1$ and $k_2$ we need to know $4$ bits of the main key. To guess $k_1$, $k_2$, $k_3$ we need $8$ bits of the main key. And in general to guess $k_1$ to $k_n$ keys we need to know $4(n-1)$ bits. So $n$-th key is defined by $4$ bits, exept first key $k_1$. Let's assume that realationship between $508$-bit main key and $k_1$ to $k_n$ keys are quite easy. So if you have $k_n$ you can find $4$ right bits in main $508$-bit key.
What do you think about that kind of encrytpion scheme? It looks like we ain't got here any differentials (as far as I study it). But we can easy imagine way to attack it in one round. For example to know $k_1$ you can only encrypt one number and then you know what are all least significant bits in all $0$ to $2^{127}-1$ numbers and in $2^{127}$ to $2^{128}-1$. Then we can try to find $k_2$ and guess bits of main key, quite easy. It looks like it is very easy to find encrytpion scheme in least signifficant bits. But to find all keys $k_1$ to $k_{128}$ we need very much plaintexts. And if we will do many rounds it isn't that easy even to find encrytpion scheme of least signifficant bits.
Do you think that there is a chance it will be resistant to known crypto attacks? What method of attack could be best to attack it? Maybe you can give some practical example?


texts: How to compare between two cryptographic algorithms in terms of security?

texts: How to compare between two cryptographic algorithms (e.g. SHA-1 and SipHash) in terms of security? That is, how could one prove that algorithm X is more secure than algorithm Y?


texts:
I have been searching about if it is more secure to use CBC mode in OTP but I can't find anywhere where people have sad that it is more secure.

Question: Is CBC mode in OTP more secure?

Because I have been reading articles like "https://stackoverflow.com/questions/22212407/how-to-alter-cbc-encrypted-text-to-change-the-message" and I have been wondering if it makes OTP more secure on that attack.

For example, let say that you have a message: "100 dollars should be moved." and you encrypt it with OTP. Then everybody can just take the first character "1" and change it to a 9 by XOR the 1 from the cipher-text and then XOR a "9" with the key you got.

BUT if you have it in CBC mode does it make it safer from this kind of attacks? (Known-plaintext-attacks and chosen-plaintext-attacks).


texts: What's the fundamental difference between Diffie-Hellman and RSA?

texts: What is the difference in the purpose of DH and RSA?  Aren't they both public-key encryption?


texts:
I am a programmer, so when I hear XOR, I think about the bitwise operator (e.g. 0110 ^ 1110 = 1000).

The mention of "XOR" comes up quite a bit in cryptography. Is this the same XOR as the bitwise operator? If so, how is it used to encrypt a large amount of data rather than just an integer? Wouldn't you need the "password" to be the same length as the data you are encrypting?


texts: Asymmetric algorithm with indefinite number of public keys

texts:
So RSA algorithm uses pre-generated set of public and private key, and public key is usually included in private key. So public key stays always the same.

Is it theoretically possible to have some algorithm that has one private key and indefinite number of public keys that can be generated on-demand?

Assume we have goals

Decrypt/verify data signed with single private key by using any of public keys
Encrypt data using any of public keys and decrypt with single private key
Probably also same stuff vice versa (multiple private keys, single public key)

Can any of these goals can be achieved theoretically? PGP and RSA just generates constant set of keys from what I seen just now.

CA is also not an answer to my question because CA equals having single public key of root certificate, not indefinite amount.


texts:
The NORX8 paper says

  It is assumed that adversaries are nonce-respecting.

What is a nonce-respecting adversary?


texts: Calculate RSA private exponent when given public exponent and the modulus factors using extended euclid

texts:
I was reading this  answer that shows how to calculate the inverse of public exponent, i got to the point where we apply the euclidean algorithm and finish substituting to get

(40−2×17)−1×(17−2×(40−2×17))=1

it states "this is a linear combination of 17 and 40, after simplifying you get:"

(−7)×17+3×40=1

which gives us the d = -7

but i'm stuck as to how we simplified down to

(−7)×17+3×40=1

from:

(40−2×17)−1×(17−2×(40−2×17))=1

i would be grateful if someone could explain it to me

Thanks in advance


texts:
RFC8032 Edwards-Curve Digital Signature Algorithm (EdDSA) 5.1.3 Decoding states the following:

  Decoding a point, given as a 32-octet string, is a little more
  complicated.

  First, interpret the string as an integer in little-endian
     representation.  Bit 255 of this number is the least significant
     bit of the x-coordinate and denote this value x_0.  The
     y-coordinate is recovered simply by clearing this bit.  If the
     resulting value is >= p, decoding fails.

My questions are...

32 octets is 256 bits. I'm assuming the index of the first bit is 0 instead of 1, which would make 255 the last bit. So why not say that it's the last bit instead of the 255'th bit?
Quoting the previous section, "To form the encoding of the point, copy the least
significant bit of the x-coordinate to the most significant bit of
the final octet.". So to encode we set the most significant bit and to decode we look at the least significant bit? So we're not looking at the same bit? That doesn't make a lot of sense to me.
When you interpret the string as an integer I'm assuming you're supposed to interpret it in two's compliment? eg. where if the first bit is 1 then you assume that the number is negative? The RFC isn't at all clear imho..


texts: Understanding a method of vector multiplication

texts:
Recently, I attempted to implement the HQC Post-Quantum KEM in (almost) pure python. In the scheme specification whitepaper, it states the following:

Here is a simplified version of the function I used to calculate the vector product (the actual function is implemented using bit-twiddling but this makes it more readable):
def _convolute(b, a, l):
        aa = [int(c) for c in ('{0:0' + str(l) + 'b}').format(a)]
        bb = [int(c) for c in ('{0:0' + str(l) + 'b}').format(b)]
        out = [0] * l
        for i in range(l):
            if (aa[i] == 0):
                continue
            for j in range(l):
                out[(i + j) % l] ^= bb[j]
        return int(''.join([str(c) for c in out]), 2)

Here, l, is always going to be the cryptosystem parameter $n$. This is an attempt at implementation of the vector product method described above. The vector a is always going to be incredibly sparse (~100 1s), so the naive method works fine. I believe the actual implementation uses a constant-time method to avoid SC timing attacks, but I'm not too concerned with that now.
I implemented this, and the cryptosystem worked as expected, encryption and decryption were correct, and the essential arithmetic given in the correctness proof section of the whitepaper was also correct, so I didn't give it much thought.
However, revisiting the project I decided to actually test all the functions against the KAT data given in the submission package. From the 04/10/2019 submission, I checked against the hqc-256-3 data for the reference implementation.
For the values of x, y, and h given in the data, the value of $s = x + y \cdot h$ does not match against my implementation, so I decided to take a look at the function again. Using Sage to perform arithmetic in the quotient ring $\mathcal{R}$ defined in the whitepaper, my _convolute function does not agree with it (using the interpretation that vector bits correspond to coefficients of the polynomials). I can't check against the reference data as Sage appears to do the calculations too slowly and cannot take advantage of sparse polynomials, so I was using elements of smaller degree for testing.
In conclusion, where am I going wrong? Am I correctly interpreting/implementing the vector product method in the whitepaper with the convolute function? Is a direct comparison to multiplication in $\mathcal{R}$ misguided? Lastly, would anyone be able to provide an algorithm which definitely works for computing products in $\mathcal{R}$, preferably without using FFT or similar, and just done in a schoolbook method.
In addition, if my method is completely incorrect, to what extent is the cryptosystem actually weakened by this wrong product computation?


texts: There exist protocols for 2-party computation e.g., GMW that use Boolean circuits. I could also use Paillier and arithmetic circuits for a 2 party computation. However after reading about SPDZ is my understanding I could use it to do 2-party computation. Is my understanding correct? Besides the fact that I would have to generate tons of triples, is there any other drawback of using SPDZ for 2-PC? If this is the case why is not widely use for the 2-party case? Should I favor a 3 party setting instead of a 2 party one when using SPDZ?


texts: Why do stream ciphers like A5/1 and ZUC have "frames"?

texts:
A5/1 and (I think) ZUC, both stream ciphers used in mobile telecommunications, have "frames" where the, in addition to the key, a frame number is provided to the keystream generator which produces a relatively short pseudorandom sequence called a "frame" (on the order of at most a few kilobytes).

Advancing the stream cipher requires incrementing the counter and running the algorithm again with no state carried over from the generation of the previous frame. This stands in contrast to stream ciphers like RC4, Trivium, and Grain, where the $i$th keystream bit can only be computed after generating the previous $i-1$ bits, and in contrast to counter mode and stream ciphers like ChaCha20 which are capable of complete random access.

What is the rationale behind these "frames" and why not just go for full random access if they want this?


texts:
I'm currently trying to implement the Rabin Cryptosystem when I realized something when gave p and q the same value:

So my values are as follows:

Original message = 20

p=11

q=11

Encrypted message = 37

After decryption I get four values

99, 99, 22, 22

None of the values are my original message. Why is that, and how can I still get the original message?

I implemented the algorithm following the wiki article found here: https://en.wikipedia.org/wiki/Rabin_cryptosystem

Thank you in advance!


texts: How does the split mask countermeasure work on AES?

texts:
I am trying to understand the split mask countermeasure which is a masking method to avoid side channel attacks. Let's first describe the principle and then try to apply it to AES.

I found this paper which analyses this method. First, I will quote the presentation of the split mask countermeasure which is given in the second section:

  Let $S$ be an S-box with input $x$ and output $S(x)$ implemented as a
  lookup table. The split mask implementation of $S$ consists of a
  masked table $S′$ and a mask table $M$. These tables are defined as
  follows: \begin{equation} S'(x \oplus n) = S(x) \oplus r_x,
 \hspace{1cm}\\ M(x \oplus n) = r_x \oplus m \hspace{1cm}(1)\\
 \end{equation}

  This means that the input of the S-box is masked with $n$, and each
  output value is masked with an individual random value $r_x$. This
  gives the masked table $S'$. The set of output masks $r_x$ is also
  stored in the mask table $M$ so that
  \begin{equation} S'(x \oplus n)
 \oplus M(x \oplus n) = S(x) \oplus m \hspace{1cm}(2)
\end{equation}
   holds for every input $x$. In other words, $m$ can be viewed as the
  output mask of $S$ that is split into two shares $r_x$ and $M(x \oplus n)$, the splitting being individual for each table entry.

  The split mask countermeasure with a single mask table is claimed to
  thwart the 1-st order DPA attack. For this, the original description
  requires that $(2)$ should never be computed directly (i.e. appear
  as an intermediate value) during an algorithm execution.

The description seems clear to me except this sentence:

  For this, the original description
  requires that $(2)$ should never be computed directly (i.e. appear
  as an intermediate value) during an algorithm execution.

So how should it be computed?

So let's consider we want to encrypt a block data using AES and the split mask countermeasure. We start by generating $n$, $m$ and 256 bytes $r_x$ to compute $S'$ and $M$.

But then, when we have to apply the $\texttt{SubBytes}$ operation during the algorithm, how to proceed?

In the same paper mentioned above it is said:

  Other details of concrete implementations can be found in [10, 11, 12, 13]. In these papers the countermeasure is proposed for an optimized
  AES implementation with $8 \times 32$-bit lookup tables that are used
  to compute the S-box and the diffusion simultaneously.

but it concerns optimized $32$-bit implementation and I would like to simply implement it for a traditional $8$-bit version so it does not help me that much...


texts: Probabilistic verification of signature schemes like RSA?

texts:
I was wondering if there were any verification algorithm in the literature that enables a "probabilistic" verification of well-known signature schemes?

For RSA signature verification for example, is there any way to verify $s^e = H(m) \mod N$ in a fast way but with a certain "error" probability ?

If not for RSA, for any other schemes ?


texts: Partially homomorphic addition - not all parties present

texts:
I often see homomorphic encryption as a solution to a problem where a server wants to know the sum of $n$ users' numbers but can not know each individual users' number plaintexts.

My question is: if $n=10$, and only $9$ of the ciphertexts are reported, can the server decrypt the sum of those $n-1$ ciphertexts?

Furthermore, do the $n$ users' keys depend on the server's 'master key'?


texts: key specifications for x25519 - need two clarifications please

texts:
Am implementing x25519 (in 64 bit and 512 bit assembly) following the specifications in RFC 7748 (and its errata list !).

Need two clarifications please.

The private key is randomly generated 32 byte string with MSB set to 0 and MSB-1 set to 1, and, last 3 bits set to zero. Now, once a random 256 key has been generated, it is made compliant to these specified requirements, and the corresponding public key has been computed. The clarification being sought is : does the private key remain this 32 byte string after the MSB/MSB-1 is set ? Does this imply that the actual count of universe of random private keys is restricted to 2^251 (256 - MSB - [MSB-1] - 3 LSB - all these bits are fixed) ? If an external user were to specify a key that is not compliant with this requirement, and the software modifies it to become complaint, does the external user specified private key needs to be updated with this post compliant string ?
Most implementers (e.g. Michael Dull (apologies for not being able to type the umlaut in the surname) et. al. in paper "High speed Curve25519...") have mentioned that the last inversion  step (Z^(p-2)) requires 254 squaring steps and 11 multiplications. I understand the 254 squaring steps, but am not sure what algorithm is used to restrict the count of multiplications to such a small number. If this is not a state secret, can I be directed towards the actual algorithm that generates the inversion mod p-2 with (just) 11 multiplications ?

Thanks for your attention and time.


texts: How to securely map messages to points on an elliptic curve

texts:
I'm implementing a demonstration hybrid cryptosystem in Python (FinCrypt, I know the name is bad) and I'm migrating over from my Weierstrass curve implementation, which was based off of this, to one based on Edward's curves from here.

However, I'm at a loss when it comes to mapping a message onto an element of the elliptic curve, and I noticed that the implementation I'm currently using doesn't require the message to be mapped, at least to my knowledge.

I was wondering three things:

Do I have to map a message, or is it possible to do something like I've already got going with Edward's curves
Is my current implementation of the ElGamal part insecure because it doesn't map messages and instead takes an integer?
If I do have to implement a mapping for security, how would you reccomend I map message values to points, and how should I figure out the maximum message size based on my curve?


texts: Is it possible to permute a binary vector obliviously?

texts: Lets say A has a binary vector of length n, B has a permutation matrix of size n. Is there a way for B to permute A's vector so that A only learns about the result of permutation and B does not learn about the original vector?


texts: Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset

texts:
Suppose $g$ is a generator of an order $p$ cyclic group in which discrete logarithm is hard and $p$ is a prime (i.e., given $g^x$ for a random $x \in \{0,1,\ldots, p-1\}$, it is hard to recover $x$ except with $negl(\lambda)$, where $negl(\lambda)$ is a negligible function of the security parameter $\lambda$).

My question is as follows: what happens if I am given $g^y$ such that $y$ is chosen randomly from $\{0, 1, \ldots, q-1\}$ for some $q < p$, is there a way to quantify the hardness of discrete logarithm in terms of $q$? perhaps, something like: probability that one recovers $y$ is at most $\frac{1}{q} + negl(\lambda)$ and the probability is taken over the choice of $y$, or is there no way to quantify this?

I am mainly interested in knowing what happens in practice when one does this. For instance, in most libraries, the exponents are chosen to be 160 bits even though $p$ is 1024 bits.

(I posted this on math.stackexchange, but no responses. So, I am moving the question here by deleting it from there.)


texts: Toy encryption system that provides "hints"

texts:
I'm looking for a toy encryption system that has a specific property that when decrypting it with a key that is close enough to the key used in the encryption, it will produce some of the original plain text.

The idea is to use it as a game/teaching system where kids can try to break a cyphertext but instead of using cryptanalisys on the cyphertext, I want them to try different keys and then the decrypted text would provide feedback as of how close the key really is, for example:

I encrypt

attack at dawn with key 1234

and let's say the cyphertext is

ABCDEFGHIKLMN

now, if I try to decrypt the cyphertext with key, for example, 1288, it should display some of the plaintext, in order to hint the breaker that the key is somewhat close to the real one

think of it as an encryption system a la Mastermind

A simple substitution cipher kind of does the trick, but I'm wondering if there are other ciphers that behave that way (preferrable with smaller key space)


texts: Does there exist a universal one-way permutation?

texts:
Leonid Levin constructed a universal one-way function, i.e. a function which is one-way as long as there exists at least one one-way function.
But my question is, does there exist a universal one-way permutation, i.e. a function which is a one-way permutation as long as there exists at least one one-way permutation?  Would a modification of Levin’s construction achieve this?


texts: What math makes it safe to offer a stolen-password check service?

texts:
The database provider HIBP has 4 billion stolen passwords, and wishes to offer an API for websites to use during new-user signup (and password change) operations, so they can refuse to allow users to select a password that is known to have already been stolen.

HIBP is not trusted.

Does a way exist for a website to ask HIBP some question, and receive some result, that never allows HIBP to determine the password being inquired about (including against dictionary attacks) assuming that the password is NOT in the database.
Is the above possible, even if the password is in the database?  e.g. can I check HIBP for existence of the string "password123", and get a result that I can understand means "yes, that exists", but which leaves HIBP with no way to know what string I queried, nor whether it was found?

This sounds like an interesting homomorphic challenge to me, but I don't know this field in depth.


texts: CBC-MAC 8 octet ICV compatable with 16 octet block size?

texts:
I'm trying to use DTLS in Preshared key mode for CoAP which necessitates using CipherSuite TLS_PSK_WITH_AES_128_CCM_8

I'm trying to start with the CBC-MAC but I'm not sure how to get an 8 octet ICV out of it?

Do I just truncate the output and only use the first 8 octets?

Do I use an 8 octet block size instead of the 16 imposed by the CBC function I'm using for hardware acceleration?

const unsigned char k[16] ="lbsHgUDHKgeinLfU";//key 128bits

const unsigned char message[16] = "Hello world!  ";//multiple of 16 bytes as required
unsigned int mLen = sizeof(message);//16

unsigned char zeroInit[16]= {0};

//CBC-MAC with 8byte ICV
//uint8_t mac[8];//8 octet ICV (hopefully)
uint8_t mac[16];

esp_aes_crypt_cbc( &c,ESP_AES_ENCRYPT,mLen,zeroInit, message, mac);

and the output I get is:
ad  ea  26  07  25  bb  43  8a  85  b5  ec  ca  6c  b6  b5  d3

The only difference I see with an array size of 8  is that I only see the first 8 bytes.


texts: How to find fixed points for DES weak keys

texts:
Can someone explain me this  please I am a bit confused?  It's from a texbook I am reading (block cipher companion)  it says that:

  each weak key has  $2^{32}$ fixed points $m$ where $\operatorname{DES}_w(m) = m$ ( $w$ is a DES weak key). In other words encrypting a fixed point gives exactly the same point. To see this consider the $2^{32}$ ciphertexts after 8 rounds of encryption for which the two 32 bit halves are equal. For a weak  DES key, the round keys of the eighth and ninth rounds are equal. Thus the intermediate texts after seven rounds and after nine rounds of encryption will be equal. Since the round keys of the 7th and the 10th rounds are equal, the intermediate texts after 6 rounds and after 10 rounds of encryption will be equal. Continuing like this it follows that the plaintext will be equal to the ciphertext.

Now did not quite get :

Why are there $2^{32}$ fixed points?  And why after the eighth round of encryption the two halves must be equal?
What does the author mean by the intermediate texts exactly? And how are they being equal?

P.S.: This question is not asking for what the weak keys are. I am asking for "fixed points" not exactly weak keys. For this reason I think it is not a duplicate of any other question. There is one similar question to what I've asked for which I have checked and saw that no satisfactory answer has been given there either.
Here is the similar question with no proper answers:

What is the fixed point attribute of DES with weak keys?


texts: What if we increase the key length of DES and use ECB Mode, then will we get the different output as ECB mode encrypt with the same key?

texts: I am looking for an answer as if we have DES having 64 bit key and we are encrypting an image it with ECB mode but it doesn't encrypt well. so if we change the key length then will it effect the output or not?


texts: How do ciphers change plaintext into numeric digits for computing?

texts:
For example, in RSA, we use this for encryption: $ciphertext = (m^e \mod n)$  and for decryption.

If our message is "hello world", then what number do we have to put as $m$ in the RSA formula?


texts: Request for review: known plaintext mitigation by rotation and xor encoding

texts:
When using structured data inside a plaintext (such as gzip headers, xml, etc.) they generate known plaintext which may be useful in cracking the ciphertext.

So I had these two ideas on how to make this known structure less useful to attackers while preserving the value to those with valid decryption keys:

First, if we prepend zero use a random xor, when decrypting we can remove the first value and xor the remainder of the text by that value it may make decrypting the ciphertext somewhat more difficult as the known plaintext is somewhat varied.

The second idea is to just rotate the start of the message by a random amount putting the known plaintext at a random place in the block (obviously less useful with streams). By prepending the coded plaintext with the offset with the original message can easily be recovered without introducing a known plaintext as the offset is a random number).

Further these two methods can be combined. Obviously these would add no cryptographic value to texts without known substrings and are completely useless without being paired with a real cipher.

The question is how useful would they be in mitigating a known plaintext attack?


texts: Is the nonce in GCM mode used as key for HMAC? And how to send it?

texts:
So, my believe is that, in some way, GCM mode or any other authenticated encryption mode is useful to provide encryption and integrity for the ciphertext altogether instead of having to handle the encryption en HMAC separately (as in CBC + HMAC).

My confusion, and this might be a little bit directly related to Java API.., is that using GCM mode I can specify:

a nonce,
AAD data

So, my questions:

Is the nonce used to generate a "probabilistic ciphertext", as with IV in CBC mode?
Is the nonce also used as key to generate the HMAC for the ciphertext? And therefore only specifying this one I would already obtain an authenticated ciphertext (without having to specify the AAD data)?

Or is the AAD data the one used to generate the HMAC for the ciphertext (I'm pretty sure it's not)?
And if not, what is the AAD used for? "To provide an additional context HMAC to accompany the ciphertext"? Could somebody provide an example of this?

ALSO.., independently of which element is used as key to generate the HMAC for the ciphertext..
How must this one be protected?
As far as I know, the nonce does not have to be random, it can be a numeric sequence like 1, 2, 3.. for each encrypted message. This seems pretty guessable by an attacker. So isn't it dangerous to use a guessable nonce, or even send it in clear with the cyphertext?

Thank you, and forgive me if I have misused some cryptography terms or words.


texts: In the SHA hash algorithm, why is the message always padded?

texts:
In the SHA hash algorithm the message is always padded, even if initially the correct length without padding; the padding is of the form "1" followed by the necessary number of 0s.

Why is it necessary that the message always be padded?


texts: Should the field size in Shamir secret sharing scheme be larger than secret?

texts:
I'm playing around with implementing Shamir's secret sharing scheme in Kotlin.
Here is implementation so far:
fun main(args: Array<String>) {

val a = 10.0.toBigDecimal()
val b = 10.0.toBigDecimal()
val c = 7.0.toBigDecimal() // secret
val field = 20.0.toBigDecimal()
 fun polynomial() : (BigDecimal) -> BigDecimal =
    { x : BigDecimal -> ((a * x.pow(2))+(b*x)+c).remainder(field)}

fun generateShares(one :BigDecimal, two : BigDecimal, three :BigDecimal): List<Pair<BigDecimal,BigDecimal>> {
    var shareSet = arrayOf(one,two,three)
    return shareSet.map { x ->  Pair(x, polynomial().invoke(x)) }
}

val shares = generateShares(1.0.toBigDecimal(), 2.0.toBigDecimal(), 3.0.toBigDecimal())

fun langraged(cord0 : Pair<BigDecimal,BigDecimal>,cord1 : Pair<BigDecimal,BigDecimal>,cord2 : Pair<BigDecimal,BigDecimal>) : (BigDecimal, BigDecimal) -> BigDecimal{
    val L0: (BigDecimal) -> BigDecimal = { x -> ((x - cord1.first)*(x - cord2.first)) / ((cord0.first - cord1.first)*(cord0.first - cord2.first))}
    val L1: (BigDecimal) -> BigDecimal = { x -> ((x - cord0.first)*(x - cord2.first)) / ((cord1.first - cord0.first)*(cord1.first - cord2.first))}
    val L2: (BigDecimal) -> BigDecimal = { x -> ((x - cord0.first)*(x - cord1.first)) / ((cord2.first - cord0.first)*(cord2.first - cord1.first))}

    return { x, field -> // This lambda is what I am asking about
        val resser = cord0.second * L0(x) + cord1.second * L1(x)  + cord2.second * L2(x)
        if (resser < 0.0.toBigDecimal()){
            (resser % field) + field}
        else {
            resser % field
        }
    }
}

val constructedPolynomial = langraged(shares[0], shares[1], shares[2])

val reConstructedSecret = constructedPolynomial(0.0.toBigDecimal(), field)

println("and we reconstruct f(0) as: " + reConstructedSecret)

}

So the gist of my question here is about the usage of my field size, that I use for modulo.
With this implementation, if I choose a field that is larger than my secret then I will only be able to reconstruct the part of the secret that is remainder after dividing by the field size.
In other words, In order to reconstruct my polynomial, when using a field I have to return
result % field

So for example, if my field is 50, and my secret 51, then my reconstructed secret is 1.
So, in order to use Shamir's scheme with  a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?


texts:
I've been trying a long time to understand a thing which is obviously extremely simple, but I just can't get it.
Read this, please:

The NTRUEncrypt PKCS uses the ring of truncated polynomials $R$ combined with the modular arithmetic described in Section 1. These are combined by reducing the coefficients of a polynomial a modulo an integer $q$. Thus the expression $$a \pmod q$$ means to reduce the coefficients of $a$ modulo $q$. That is, divide each coefficient by $q$ and take the remainder. Similarly, the relation $$a \equiv b \pmod q$$ means that every coefficient of the difference $a-b$ is a multiple of $q$.

This is taken from NTRU tutorial and that's quite understandable. But. Take a glance at the next excerpt from the same tutorial:

The inverse modulo $q$ of a polynomial $a$ is a polynomial $A$ with the property that $$a * A \equiv 1 \pmod q.$$
Not every polynomial has an inverse modulo $q$, but it is easy to determine if $a$ has an inverse, and to compute the inverse if it exists. A fast algorithm for computing the inverse is described in NTRU Technical Note 014, and a theoretical discussion of inverses in truncated polynomial rings is given in NTRU Technical Note 009. These notes may be downloaded from the Technical Center.
Example. Take $N=7$, $q=11$, $a=3+2X^2-3X^4+X^6$. The inverse of $a$ modulo 11 is $$A=-2+4X+2X^2+4X^3-4X^4+2X^5-2X^6,$$ since $$(3+2X^2-3X^4+X^6)*(-2+4X+2X^2+4X^3-4X^4+2X^5-2X^6) \\ = -10+22X+22X^3-22X^6 \equiv 1 \pmod{11}."$$

I do not understand how $-10+22X+22X^3-22X^6$ may be 1 (modulo 11). Why???????
The first excerpt adduced says that each coefficient of the polynomial minus 1 must be a quotient of 11. But it's not.  -10? That's not a problem. $-10 - 1 = -11$.  $-11 \bmod 11$ is 0, yes, it works, I agree. But how can it work with 22? $22 - 1 = 21$. $21 \bmod 11 = 10$, not 0. also it doesn't work with $- 22$. $-22 - 1 = -23$. $-23 \bmod 11 = -1$.  Can anyone, please, explain me this example?


texts:
Suppose $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$
$$F'(k, x) = F(F(k, 0^n), x) \; $$
Trying to get the intuition to prove it is secure PRG else given will be not by contrapositive...
but cannot from the reduction of it. How to formulate it to prove it is secure?


texts: Is it safe to split the output of PBKDF2?

texts:
I would like to know if splitting a key generated by PBKDF2 to derive two keys is a safe practice.

Concretely, in my system, I need to derive two keys. One for symmetric cipher used in the client side, and one for authenticating the user by sending to the server. The first key is never sent to the server so that only the client knows how to decrypt ciphertexts.

User enters email and password;
Derive k <- pbkdf2(password: password, salt: email, alg: 'sha256', iteration: 10000, dkLen: 512);
Split k into (k0, k1) = (k[0:255], k[256:512]). Use k0 as client side key and send k1 to the server.

My idea is that there is no risk in splitting the key in such manner because the key is a pseudo-random string. Any ideas?


texts: Can you defeat AES-CTR's birthday boundary with a 2nd AES?

texts:
This follows on from How do I produce a stream of secure random numbers from AES-Counter mode?

Consider then the generator:-

$$
 \operatorname{AES_{k1}}(n) \oplus  \operatorname{AES_{k2}}(n)
$$

where    $  k1 \ne k2  $, and  $n$ is the single counter variable. And we take care to ensure that there is no relationship between $k1$ and $k2$. If this  really does create a pseudo random function, will the  birthday boundary for AES-CTR output be overcome?


texts: RSA: Fermat's Little Theorem and the multiplicative inverse relationship between mod n and mod phi(n)

texts:
I'm learning about the proof of the RSA encryption algorithm, and I'm clearly fudging or missing something, because for me it doesn't add up.

When generating keys for RSA encryption, we make sure that:
$ed \equiv 1\pmod{\varphi(n)}$

But when encrypting or decrypting, we use:
$C \equiv M^e \pmod{n}$

Now I would understand if we had made:
$ed \equiv 1 \pmod{n}$

because now raising $C$ to $d$ will get us $M$ again.

But we use $\varphi(n)$ instead.

I understand that we use $\varphi(n)$ to make $d$ difficult to compute, since to find $\varphi(n)$ you need to know the prime factorisation of $n$.

But how do you link a multiplicative inverse mod $\varphi(n)$ with a multilicative inverse mod $n$?

From reading around it seems that according to Fermat's Little Theorem, a multilicative inverse mod $\varphi(n)$ will hold mod $n$.

If a multiplicative inverse relationship works for $\varphi(n)$ and $n$, why does an attacker not work out the multiplicative inverse of $e \pmod{n}$? Even if the key were originally made mod $\varphi(n)$, surely using an inverse mod $n$ would work just as well?

Clearly I'm missing something - could someone please help enlighten me?


texts:
I want to construct a hash-chain where I want to share millions of small AES-128 keys with Bob over a period of time. Bob should not be able to predict the future keys if he knows the past keys. I also want to avoid having Bob storing all these keys, but rather be able to derive them so that if they know the key from time $t$, they should be able to derive the keys from time $t-1, t-2$, and so on. So, future-to-past derivation should be possible. Past-to-future derivation should be hard.

The hash-chain way of doing this is to start with a random string, hash it with sha256, say, 1 million times, and start the chain with the 1 millionth hash. This way, if Bob is at the 10th iteration of our protocol, and wants to go back to the 6th iteration, he hashes the 10th iteration key 4 times to get the 6th key.

I am wondering if we can do the same with some encryption scheme like RSA. I give Bob my RSA public key $([e, n])$. I start the chain with a large random number in the range $(2, n-1)$, and decrypt it. I am assuming that every number in this range has a valid decryption. This decryption chain can continue as many times. If Bob wants to reconstruct keys, he uses the encryption algorithm, for which he has the public key. I can use some KDF to derive the AES-128 key from this large RSA "number".

Is the RSA-chain scheme as safe as the SHA-chain scheme?


texts: How to check that you got the right key when brute forcing an encryption?

texts:
How do you know when you have the right key when brute-forcing? Let's say that they test the right key. They then have to check that the decrypted text makes sense.  To do so, they can test whether there is a word in the dictionary.

But then let's say that the message is encrypted with Enigma then with RSA encryption. They try to brute force the RSA encryption but how do they do to know that they got the right key, since the text itself is encrypted with Enigma and has no word contained in the dictionary ?


texts: Discrete Logarithm Problem or just integer exponentiation problem?

texts:
In reading the following paper,

https://ai2-s2-pdfs.s3.amazonaws.com/35eb/afbaab34223bca50a7be2f5915fddf918fc7.pdf

Generate two primes $p$ and $q$ such that $q|p-1$. Pick a generator $g$ of $Z_p^{*}$. $g$ is declared as public.

$c_1=g^r$ where $r \in Z_q^{*}$

As far as I understand, $g$ is integer ranging from 0 to p.
If there is another meaning for $Z_p^{*}$, please let me know.

Given $g,c_1$, find $r$.

Is it discrete logarithm problem? or just integer exponentiation problem?


texts: A multi-target attack on 128-bit ECDSA private keys

texts:
I'm thinking about doing this as a project, but I'm not sure how I'm supposed to proceed.

So I have an 128-bit ECDSA, which would provide about 128 bits of security (if we do not use special methods like the baby-step giant-step algorithm or Pollard Rho's algorithm). I generate a list of 2^64 public keys, and I want to find the private keys to any one of them.

So essentially this is a multi-target attack on ECDSA private keys. With 2^64 targets (public keys), I would require 2^128/2^64=2^64 attempts on average to find a private key to any one of these targets.

I have a few questions:

(1) How long would it take for a computer to perform 2^64 ECDSA operations? Is 2^64 within the realm of possibility using commonly-available GPUs?

(2) I need to generate a list of 2^64 public keys (targets). Then I need to create a database for these keys, and index them (based on their x coordinate number size, in order to perform a structured search/lookup). Therefore, the size of this database would be bordering on several exabytes, which is completely infeasible using commonly-available resources. Is there any way to reduce the size of this database?


texts:
I'm looking into "bitcoin like" mining processes. Say a security process uses a hash of data as proof that the data was known at some point in time.

From what I understand, hash functions are pseudorandomly generated based on the initial seed (the raw data).

If the hash function is chaotic, then the seed data should have strange attractors. If so, then I may be able to map a seed to its attractor and "pre-mine" using attractor buckets.

Are these pseudorandom functions "deterministic chaotic systems"?


texts:
I am looking for data which shows how time it would take to brute force (or crack by any other method) different sizes of RSA/DSA keys used for a digital signature.

I am looking to use as small a key as possible & hence looking for how long a signature generated by it can be cracked.


texts: Are there any additively homomorphic encryption schemes over $\Bbb Z_2$ besides Goldwasser-Micali?

texts:
I am aware of Goldwasser-Micali cryptosystem, which is additively homomorphic over $\Bbb Z_2$.
Are there other schemes that satisfy this property?

Note: If one is willing to involve advanced tools like lattices one could get something stronger like FHE. I am looking for a simple cryptosystem not involving lattices or similar tools.


texts: Can we protect PRESENT from the Statistical Saturation Attack if we change the permutation layer to a random permutation layer?

texts:
This is continuation-question based on: If PRESENT had different permutations s would that protect it against Statistical Saturation Attack?
Can we protect PRESENT from Statistical Saturation Attacks by using:

unique perms for each round or just some rounds? (In this case, how many might some have to be?)
random, key-dependent (say), perms for some or all rounds?

Moreover, if these ideas can indeed protect PRESENT against SS attacks:

Could we use fewer than 31 rounds without causing vulnerabilities to other attacks?

See also
What affect does the permutation layer have on the avalanche effect?


texts: An example of of an information theoretically secure protocol that is not cryptographically secure

texts:
Does there exist a protocol $\pi$ for some functionality $F$ which is information theoretically secure protocol that is not cryptographically secure for some threshold number of corrupt parties? Intuitively, such a protocol cannot exist, because if a protocol is not secure in the presence of a poly time adversary, then it must be insecure even in the presence of an adversary with unbounded computational power. However, I have constructed a protocol $\pi$ for a functionality $F$, which seems to be information theoretically secure protocol but not cryptographically secure.

Consider three parties $P_1, P_2,P_3$ with private inputs $p,q$ and $\phi$ respectively, where $p$ and $q$ are prime numbers. They wish to compute the functionality $F(p,q,\phi) = (\phi,\phi,p*q)$ i.e. party $P_3$ must receive the product of the two prime numbers as the output.

I design the following protocol to achieve the functionality: Party $P_1$ sends $p$ to party $P_3$ and party $P_2$ sends $q$ to party $P_3$. Party $P_3$ computes the product $p*q$.

The view of party $P_3$ in this protocol is $(p,q,p*q)$, where as its view is only (p*q) in an ideal implementation of the functionality $F$. Let consider the case where $P_3$ is an adversary (with no coalitions). If $P_3$ has unbounded computational power, then the two views are equivalent, and hence the protocol is information theoretically secure. Whereas, if the adversary can run only efficient algorithms (polynomial time algorithms), then the view of out protocol $\pi$ given more information that the ideal implementation of $F$, assuming factoring to be a hard problem.

My doubts are the following:

(1) Am I right to conclude that the protocol $\pi$ described above is information theoretically secure but not computationally secure, in the presence of one corrupt party.

(2) Does the simulator $S$ designed for showing the equivalence of an ideal implementation and a proposed implementation always need to be efficient? Is it dependent on the adversary's computational capabilities?


texts: Is a symmetric encryption key derivable using the input and the output?

texts:
I am looking for a python library for encrypting a string with a single key. I do not want the key to derivable by knowing the input and the output. I have came to cryptography.fernet so far, but I am not sure if this will fulfill my needs. Can the encryption key be derived by knowing the algorithm (assuming the fernet algorithm in this case) and knowing the input and the output?

For example when I encrypt message A with key K and it outputs B, can somehow A and B be put together, so it will output K?

EDIT

The actual use of this is the following. I need to store a password in a place that others can see (a discord config channel, but that is secondary) in a way so they cannot see the actual password. I thought that the user would encrypt the password one-time with a key only visible to the bot (a discord bot) (with a command). The encrypted password would then be sent back to the user and stored in the channel for the bot to decrypt it and use it later. The problem is: if the user knows the input and the output, if he would be able to guess the key, he would then be able to decrypt all other passwords stored this way. And absolutely noone wants this to happen!


texts: How does the IV or initial counter increase internally for each block in AES CTR mode?

texts: I am working on Intel AES-NI library and since the AES function is coded using low-level assembly instructions. I could not see how the IV or initial counter increases in CTR mode. In general, how does the IV or initial counter increase by itself for each 128-bit block (let's say we use AES_CTR_128)? Does it increase by one or some other value?


texts: GCM mode of operation and IV size less 96 bits

texts:
GCM specification defines the initial counter value $Y_0$ for encryption/decryption operations as follows:
$$
Y_0=\begin{cases}
IV||0^{31}1 &\text{if len}(IV)=96\\
GHASH(H,\{\},IV)& \text{otherwise}
\end{cases}
$$

I don't understand why hashing with $GHASH$ is used for $len(IV)<96$. Suppose I am using 64-bit deterministic IV's; it seems logical to create  128-bit deterministic initial counter value as
$$
Y_0=IV||0^{63}1
$$
I believe it does not contradict GCM specification. Why the specification suggests to use pseudorandomized initial counter value?


texts: RSA public key exponent generation confusion

texts:
Quote from Wiki:

  $e$ having a short bit-length and small Hamming weight results in more efficient encryption — most commonly $2^{16} + 1 = 65537$. However, much smaller values of $e$ (such as $3$) have been shown to be less secure in some settings.

Does this mean that it is secure to choose the smallest possible public key exponent possible that is larger than a certain threshold, such as $65537$? If it is not so, how are values of the public key exponent generated in more secure RSA implementations?


texts: Partition attack on the possible values of RSA modulus

texts:
This is a question that arises from an exercise you can see here on breaking a bad EKE construction with RSA. However, my question does not tackle that construction.

The problem is that we work with an RSA modulus $N$ and with $e=3$ for encryption. As usual, $gcd(3,\phi(N)) = 1$. Also $N$ is a 1024 bits number. I need to reduce the possible $N$ in order to do an exhaustive search attack. It is claimed that:

  1.As $N$ is odd and between $2^{1023},2^{1024}$ then the first and last digits are ones.

  2.$N \, mod \,3 = 1$

  3.The set of valid $N$ is at least $\frac{1}{8}$ of the full space (I understand the 1024 bits)

The first is clear to me. But I don't see a good reason for the second. Even if I admit the second point then I would have removed about $\frac{2}{3}$ of the possibilities (something more because of the first point). Why is it claimed that $\frac{7}{8}$ of the possibilities are removed?


texts:
My question essentially concerns how to prove if a function is negligible. As a matter of fact, though this question might seem very basic, it seems that most of the "proofs" of negligible concern comparing the the function with another negligible function and then asserting its status via laws of negligible functions.

What I am insisting on is a direct mathematical proof of proving how functions can be proven as negligible without comparison with any other function.


texts:
suppose i have two equations:
$$ (m)^{3} \bmod n = c_{0}$$
$$(m + 2^{k}r + d) \bmod n = c_{1}$$
The values($c_{0}, c_{1}, k, d$) are known.
I wanted to retrieve r (ofc $|r| < n^{\frac{1}{9}})$
Using resultant on equations gives me equation of 9 degree.:
$$w(x) = x^{9} + 3(c_{1} - c_{0})x^{6} + (3c_{0}^{2} + 21c_{0}c_{1} + 3c{1}^{2})x^{3} + (c_{1} - c_{0})^3 \bmod n = 0$$    , where x is $2^{k}r + d$
(as usual with coppersmith method). After substitute x with $2^{k}r + d$ and  change polynomial to monic i have polynomial of 9 degree w(r).

My question is that:
How can i use coppersmith attack? I tried sagemath small_root() but it dosnt return r(it return it only in special case when d = 0, and polynomial of 9 can be cast to polynomial of 3- bc it have only nonzero coefficient on $ r^3, r^6, r^9 $. Can my goal be achieved by changing implementation of small_root or by other mathematic  transformation?

Example:

N = 55555
R = Zmod(N)
P.<x> = PolynomialRing( R, implementation='NTL' )

for k in range(1,5):
f     = (x-7)^k*(x-5)*(x-43)*(x-273)    # 7, 43, 273 are here for making 2 a root
d     = f.degree()
roots = [ r for r in R if f(r) == R(0) ]
info  = ( str(roots) if len(roots)<10
          else str(roots[:10]) + ( '... (totally %s roots)' % len(roots) ) )
print "k=%s" % k
print "          ROOTS: %s" % info
print "    SMALL ROOTS: %s" % f.small_roots()

Code above doesnt return 2 even if it meet condition for Coppersmith's method.


texts: Pollard's Kangaroo-- What is the failure probability (assuming random functions)?

texts:
I'm reading Pollard's paper on solving the discrete log problem, i.e. to find $x$ given $y = g^x$, where $g$ is a generator of the group.

He has a Kangaroo Algorithm (page 4) which allows you, if you know that $x$ is in a range of size $w$, to find $x$ in time $O (\sqrt{w})$ and constant space. Very cool. This algorithm is also well described on the Wikipedia page.

There doesn't seem to be a complete analysis of the failure probability, though. For instance, if the size of the set, $|S|=1$, then each hop will be of the same length, and so the "wild kangaroo" has a pretty good chance of escaping all the traps. So it seems that the size of the set should affect the failure probability, but this parameter does not seem to appear in any of the analysis (except maybe in some examples on page 6).

Is there a good analysis of the failure probability of this protocol? Also what set $S$ is good in practice? Pollard suggests powers of 2 but this is based on a fairly small set of possible $S$ he looked at--has any analysis since Pollard's original paper confirmed that this is a good choice of $S$?


texts: How to distinguish a transposition cipher from a simple substitution cipher only given a ciphertext?

texts:
I am working on one interesting question. There is a ciphertext that has 10,000 letters. We need to distingish whether this ciphertext was encrypted by a transposition cipher or a simple subsitution cipher.

I understand a transposition cipher will keep the identity of each letter and a substitution cipher will change the letter to something new. So, I think we could probably check the common English patterns in the ciphertext (like 'ing', 'th', etc). If those patterns exist, we could conclude that this is a subsitution cipher. Otherwise, it would be a transposition cipher. However, this answer is not convincing for me. I hope to get an answer from an expert.


texts: how much trust can we place in protocol verifiers?

texts:
I read many papers on authenticated key exchange protocols, and most security proofs are done by the authors. In this method, you can imagine that the efficiency is low. Moreover, even if you have proven an AKE protocol's security under a certain model (say eCK), you still cannot ensure the security under all other models, including real life.

This lead me to ask: Can verify protocol's with some automated tool, for example Tamarin? This would be very efficient after all. My initial worry would be whether this will be accepted by people and as convincing as the traditional way?


texts: Relaxing Semi-Honest Security in Multiparty Computation

texts:
I am currently reading Lindell's tutorial on simulation-based proofs and I am trying to understand the reasoning why the security notions are they way the are.

In simple words, in the case of semi-honest adversaries, we require that there exists one simulator for each party that can simulate the party's view based on its input and output. This simulator should produce a indistinguishable view no matter what the actual inputs (also of the other parties) to the protocol are.
If we have constructed some protocol, we prove its security in the presence of semi-honest adversaries, by following, roughly, two steps.

Define an explicit simulator for each party that outputs, based on the party's input and output, a view that is indistinguishable from a view of that party from a real protocol run.
Assume towards contradiction that the real and simulated views are not indistinguishable and construct an adversary that breaks some underlying building block, e.g. an encryption scheme, commitments, or another protocol.

Hence, as far as I understand, this indistinguishability means that no (non-uniform) distinguisher, even knowing all inputs of all parties, given a real or a simulated view for one party, can tell whether the view was simulated or not.

Assuming my understanding of this is correct, my question is, whether a weaker version of this notion would also make sense, whether it already exists, or whether it would just be equivalent to the existing notion in some way.

Imagine some, very abstract, protocol between $P_1$ and $P_2$, where each of them has its own secret key and they use semi-honest 2PC to compute some shared key based on their own keys.
Assume I have a protocol for this functionality and simulators for both parties that work for all inputs, apart from a negligible fraction of "bad" input keys.
Intuitively, such a protocol should be a secure protocol in the presence of semi-honest adversaries (I think), but according to my understanding of the definition this would actually not be the case, since there does exist a distinguisher for some negligible fraction of inputs.
Here, it seems that requirement for not having a distinguisher for all inputs is too strong.

Does my intuition make sense or is it flawed?
Is there such a relaxed notion?


texts:
For simplicity I choose two small primes for p and q.

p=3
q=11
n=33
Φ(n)=20

Now we need to find the public key e, which has to be coprime with Φ(n). For small numbers like these it is trivial, but how can it be done when larger primes are chosen?


texts: Why does NTRUEncrypt lack a formal security proof?

texts: Is there any particular reason why NTRUEncrypt lacks a formal security proof? That is, a demonstration that it achieves certain security notion (e.g. IND-CPA). I know there is a provable-secure variant from Stehlé and Steinfeld, but my question is regarding the original NTRU proposal.


texts: Is it possible to construct a $3*3$ MDS matrix in $GF(2^4)$?

texts:
I'm trying to construct a minimal MDS matrix for a toy cipher. I'm not entirely sure, how the various code parameters are tied to my block size, and how exactly is the binary matrix formed, when you have a generator polynomial.

I'm also having a hard time in understanding what's the smallest field and matrix size, where MDS makes sense.


texts:
Is it possible that we take a $PRG$ $G(k)$ of stretch $n\cdot2^n$, and read its
output as the table of a $PRF$ $F(K)$ with input and output size of $n$?

Intuitively it sounds possible however I read it somewhere that this may not be done.


texts: For an elliptic curve, what is the difference between the base field modulus $Q$ and subgroup $r$

texts:
What is the difference between the basefield modulus $Q$ and a subgroup of prime order $r$?

They are all fields, but what is their relevance to the curve they are defined upon?

How does this relate to a scalar field?

Also: Which field is the curve defined upon?


texts: Factoring an RSA modulus given high bits of a factor


texts:
I was reading on a site about the Zodiac Killer and how he used a basic substitution cipher, but instead of substituting english letters and characters he substituted symbols.

I was wondering, if you had a large enough subset of symbols to use for commonly repeating letters like E,T,S ... then by what means could someone decipher the cipher.  This is also referring to the fact that no one has yet to decipher his last message.  Obviously this type of system of cryptography would not withstand in modern computing.

I am more interested in other techniques that could be used, I also found this site '340 Cipher', which includes frequency counts.


texts: How to compute the storage cost of encrypted data

texts: Let's say I have (as an example only) 1 MB of plaintexts. I want to encrypt it using symmetric encryption algorithm (e.g. AES) and store the plaintext and ciphertext in a memory space. Does a ciphertext take the same size as its corresponding plaintext? I mean, in my example, does this mean I need 2 MB to store plaintexts and ciphertexts? Can you provide references?


texts:
In the paper regarding Curve25519, the set of public keys $q$ is $\{q : q\in \{ 0,1,2,...,2^{256} - 1\}\}$ and the set of private keys $n$ is $\{n : n\in 2^{254} + 8 \cdot \{ 0,1,2,...,2^{251} - 1\}\}$.
My main question is: Why is the structure of the public and private keys the way it is?
What I don't understand: In Theorem 2.1., $q$ is defined to be an element of $F_p$ and $q$ is also a parameter in the Curve25519 function: $Curve25519(n,q) = X_0(nQ) = s$ with $X_0 (Q) = q$. So why does the set of public keys not equal $\{q : q\in \{ 0,1,2,...,F_p - 1\}\}$?


texts: Does composing multiple substitution ciphers improve security?

texts: Will using two substitution ciphers one after the another be more secure than using single substitution cipher?


texts: Signal-to-noise ratio in differential cryptanalysis

texts: What does signal-to-noise ratio mean in the context of differential cryptanalysis, and how can one use it to derive the number of required plaintext pairs to carry out a successful attack?


texts: What does AES256-CTS-HMAC-SHA1-96 mean in relation to Kerberos?

texts:
I'm not completely clueless as to what it means, but I'd like to understand it at a higher level.

The highest encryption type used by Active Directory domain controllers for Kerberos authentication traffic is AES256-CTS-HMAC-SHA1-96.

The first part: AES256-CTS. That's AES with a 256-bit symmetric key operating in Cipher Text Stealing mode. Where does the 256 bits of key material come from?

The last part: HMAC-SHA1-96.  I get that it's using a hash-bashed message authentication code, using SHA1 for the hash. But what does the 96 mean? An SHA1 hash is 160 bits...


texts:
I have been doing some research in group and ring signature literature.
I am trying to find a ring/group signature which provide the following propriety:

Anonymity for the signer
Verifiable by a group manager
Signer in the group should be able to create the signature on their own
The construction should be based on elliptic curve

I have checked the AOS ring signature, which are almost what I need but unfortunately I didn't find a way to add a group manager or something like that.
Are AOS signature modifiable with a group manager ? Otherwise is there a scheme/research which has those proprieties?


texts:
I'm new to cryptography and I am working on R-ate Pairings on a BN Curve:

$y^2=x^3+b$ with $b$=5

with its M-type twist:

$y^2=x^3+b\beta$, and $\beta^2 = -2$.

The base finite field characteristic is P

Now, according to the paper, there is a Frobenius endomorphism

$\pi^p:(x,y)\longmapsto(x^p,y^p)$

So, for a given point:

$Q(x,y)$ on $y^2=x^3+5\beta$,

Its Frobenius map $Q`(x^p,y^p)$ should also have $(y^p)^2=(x^p)^3+5\beta$.

My calculation shows the results is $(y^p)^2=(x^p)^3-5\beta$

So where am I going wrong?

Thanks for your help.

Reference of the paper (in Chinese):

Translation of algorithm image:

$\pi_q$ as Frobenius endomorphism, $\pi_q: E \rightarrow E$, $\pi_q(x,y) = (x^q,y^q)$

$\pi_{q^2}: E \rightarrow E$, $\pi_{q^2}(x,y) = (x^{q^2},y^{q^2})$

R-ate pairing ("pair's calculation"):

Input: $P \in \mathbb{E(\mathbb{F_p}})[r], Q \in \mathbb{E'(\mathbb{F_{p^2}})}[r]$, $a = 6t+2$

Output: $R_a(Q,P)$

a) Let $a = \sum_{i=0}^{L-1}a_i 2^i, a_{L-1}=1$

b) Set $T=Q, f=1$

c) With $i$ from $L-2$ down until 0, execute:

c.1) calculate $f = f^2 \cdot g_{T,T}(P), T=[2]T$
c.2) if $a_i = 1$, compute $f = f\cdot g_{T,Q}(P), T = T+Q$

d) Compute $Q_1 = \pi_q(Q), Q_2=\pi_{q^2}(Q)$

e) compute $f = f\cdot g_{T,Q_1}(P), T = T+Q_1$

f) compute $f = f\cdot g_{T,-Q_2}(P), T = T-Q_2$

g) compute $f = f^{(q^{12}-1)/r}$;

h) output $f$.

Edit:

In step d) $Q_1$ is a point after applying the Frobenius map on $Q$.
Then in step e) there is $T=T+Q_1$
Confusion:
According my calculation above, $Q_1$ should not be on the same curve where $T$ is.
Is it correct to calculate $T=T+Q_1$?
Or is my calculation wrong?


texts: Importance of random number generation in Schnorr's signature

texts: In Schnorr's digital signature protocol (https://en.wikipedia.org/wiki/Schnorr_signature), the signing process (as described in wikipedia) requires the generation of a random bit $r$. I am wondering how necessary it is for this bit to in fact be randomly generated.  For example, what if I generate my ith $r$ as $Q(i)$ for some degree $k$ polynomial $Q$. Would the signing protocol still be secure?


texts: Can we (with just paper and math) find the prime number "p" of an RSA key?

texts: With all our tools in math, isn't it really possible to find the prime number p of an RSA key without brute-forcing it with a computer? I'm not talking about doing it in 2 minutes but doing it in a clever way that is faster than our computers. Some algorithms work really well like MSIEVE and GGNFS, but it takes too much time to proceed. Can't we really find the prime p without the help of an algorithm?


texts: Are there any post-quantum blind signature algorithms?  Since hash-based blind signature schemes have proven to by impossible (based on a response to this question) is this an active area of research or is it only feasible by using extraordinarily large pre-quantum algorithm keys?


texts: Advantages of encrypting a symmetric key with a public key vs using a fixed symmetric key

texts:
I am new to cryptography concepts.

I am trying to protect some firmware download.

Reading some Wikipedia pages, I understand that asymmetric cryptography is time consuming, so, if I want to protect my download not only for authentication (I think I understood what to do for that), but also for sniffing, I need to crypt the download with a symmetric key.

This symmetric key can be either:

fixed and known by both parties;
or it can be crypted by the source with a public key and decrypted by the destination with the corresponding private key.

What is the real advantage of option 2?

If somebody has the firmware package (or reads it while it is downloading), a lot of machinery and time, he should be able to decrypt the message anyway, because it was crypted with a symmetric key.
The only advantage I see is that once he has decrypted firmware package version 1, if the symmetric key changes in a newly released firmware package version 2 some months later, all the job must be repeated.
So what I think is that option 2 is really useful only if sent messages are frequent, so decrypting one message won't help for the subsequent ones.

Am I right? Are there other advantages?


texts: Transforming EC public key X and Y-sign into X and Y

texts:
I'm using bouncycastle which uses X and Y coordinates for public keys.

An EC public key is more compactly represented by the X coordinate and the sign of the Y coordinate.

How do I use bouncycastle to transform X and Y into X and Y-sign, and vice versa. (The curve is secp256k1 if that makes any difference.)


texts: Possible to identify cryptographic keys in non-random binary data?

texts: From my understanding, a well-generated cryptographic key would be indistinguishable from randomly generated binary data. However, I also know that most cryptographic keys do not appear surrounded only by random noise in practice but rather by structured program data. Are there any demonstrable techniques from practically identifying likely AES keys, for example, in a typical firmware binary (or device memory)?


texts: Looking for a specific cryptosystem (encryption two times with two different keys and then decryption with another different key )

texts:
I am looking for a specific cryptosystem with the following properties:

Suppose a User (Say $User_1$) encrypts a message $M$ with the key $K_1$ (the resulted ciphertext is $C_1$). Another user, say $User_2$, encrypts the ciphertext $C_1$ with another key $K_2$ (the resulted ciphertext is $C_2$).
Now, a third user (e.g., $User_3$) should be able to decrypt $C_2$ with the key $K_3$ to achieve the message $M$.

$C_1 = E_{K_1}(M)$

$C_2 = E_{K_2}(C_1)$

$M = D_{K_3}(C_2)$

Note: The keys may be related to each other, but they should be three different keys.


texts: Non-outsourceable digest-free signature scheme

texts:
Given a message $M$, I am looking for a signature scheme that does not involve first computing the digest $H(M)$ and then signing $H(M)$. Signature schemes on digests are outsourceable in the sense that the private key holder does not need custody of $M$ while signing (the digest $H(M)$ suffices and can be generated by a third party).

For context, I am trying to build a "proof of custody" scheme, where some private key holder proves he also had the original message $M$ in full at the point of signing.


texts: Difference of full codebook and non full codebook

texts:
While reading a paper about Dynamic cube attack, I saw two terms:
full-codebook and non-full-codebook attacks.
What do they mean?
What is the difference?

Regards


texts: How can a cryptosystem be unconditionally secure?

texts:
The definition of an unconditionally secure cryptosystem states that the cryptosystem cannot be broken even with infinitely computational ressources and time.
However, since most books define the keyspace $\mathcal K$ to be finite, then with infinite time any computational device can perform an exhaustive keysearch.

Why are perfect secrecy cryptosystems unconditionally secure? I mean, how can the one-time pad with a small keyspace be considered to be unconditionally secure (take ${\mathcal K} = \{0,1\}^n$ for some small $n$)?

Are unconditionally secure cryptosystems the same as perfect secrecy cryptosystems?

In order to define computational security, one makes the relaxations of unconditional security, that it is possible to break the cryptosystem in superpolynomial time and with neglible probability. Why are these relaxations of unconditional security? Any cryptosystem can be broken with small probability by taking a key at random, even an unconditionally secure one?


texts: Provable data possession (PDP) VS Merkle tree

texts:
In the paper Provable Data Possession at Untrusted Stores, there is a mechanism that allows a client to efficiently check if the server still has the client's data. They define two constraints for their system: server-side data access and communication complexity.

Also, they state that a scheme based on just Merkle tree cannot be secure (so they don't talk about the complexity here). They have cited a paper but cannot find any explanation for that.

Question: Why cannot we design a PDP using just a Merkle tree?


texts: Hash function composition - security level

texts:
When using two hash functions, g(x)=SHA-512 and f(x)=MD5
g(x) has 512 bit output (using salt)
f(x) has 128 bit output.

Let's say that z(x)=f(g(x))
meaning the output is 128 bit long.

The Question:
Is using z(x) like using MD5 with salt? Hence, the security level is low.
Opposed to using only g(x) with salt and getting 512 bit long output?

On the one hand z(x) is a more complex function than g(x) but on the other hand 512 bit should take longer time to crack vs 128 bit.


texts: Common modulus attack on RSA when the 2 public exponents differ by a single bit

texts:
This is an exam question an i have no idea how to recover the message m.

John wants to send an encrypted message to mary who has a pair of RSA keys, However, John does not know Mary's public key and so John sends an email to Mary to ask for the key. mary's email reply is intercepted by Peter who replaces Mary's public key $\{e,n\}$ with $\{e_2, n\}$ where $e_2$ is obtained by changing one bit in $e$ from $0$ to $1$. Now john encrypts a message $m$ to Mary by using $\{e_2, n\}$. As Mary cannot decrypt the message, she resends her public key to John and asks John to send the encrypted message to her again. Peter does not interrupt this time. However, Peter eavesdrops the whole communication and obtains both encrypted message (one encrypted by $\{e_2,n\}$ and one by $\{e,n\}$. Explain how Peter can recover the message $m$.

How can encryption with both $\{e_2,n\}$ and $\{e,n\}$ be used to recover the message $m$?

I did think that it is related to common module attack, but i have no idea how to prove that $\gcd(e,e_2)=1$.

Does anyone have some idea on how to recover the message?


texts: How to motivate, that in ElGamal Alice the recipient keeps her keys fixed, while Bob the sender changes the key each time - why not both of them change their keys each time?


texts: What are the constraints for an IV using AES in CBC mode?

texts:
I'm designing a protocol for use into a VPN software.

The VPN frames are encapsulated into AES-256 CBC encrypted frames. I understand that IVs must be uniquely used for each message encrypted with the same key. I believe that usually protocols generate those randomly and transmit them (in cleartext, since those are no supposed to be secret) with the ciphertext.

In my case, I wanted to avoid that because transmitting 16 bytes of IV for each VPN frame has a huge cost in bandwidth (in some cases, the size of the headers would exceed the size of the encapsulated frames) so I decided to compute those IV instead, using the following mechanism:

4.4.1. DATA messages initialization vectors

   Each DATA message relies on the session keys and on an initialization
   vector. This initialization vector MUST be unpredictable.

   That is, it is computed for each DATA message using a concatenation
   of the current session and sequence numbers. The concatenation MUST
   have the following layout (numbers are in network byte order):

                  0      7 8     15 16    23 24    31
                 +-----------------------------------+
                 |          session_number           |
                 +-----------------------------------+
                 |          sequence_number          |
                 +-----------------------------------+
                 |           must_be_zero            |
                 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+

   The must_be_zero field is a sequence of 0x00 bytes so that the whole
   frame is the size of a block for the selected cipher algorithm.

   The concatenation buffer, which is globally unique, is then ciphered
   using the target host encryption key (KE) without padding and using a
   null initialization vector.

   The resulting buffer is the initialization vector to use to (de)cipher
   the DATA message.

The complete protocol specification is available here if anyone wants to read it.

The session_number is constant for a given session (it has the same lifetime than the AES keys of the session) and the sequence number is a zero-initialized counter incremented on each send.

Doing so, I believe I have an unpredictable IV (because the attacker would have to know KE to predict the IV) and that this IV is unique (because it depends on the sequence_number which changes for each message).

I realized lately that this method was expensive in CPU time and was the cause of performance issues (because of the hash computation that seems to be the bottleneck).

So I do have two questions here:

Is my method correct (read "secure") ?
How could I do differently to avoid computing a hash for each IV while keeping unpredictability and uniqueness ?


texts:
I am looking to RFC8448 and at page 7 it says:
  PRK (32 octets):  b6 7b 7d 69 0c c1 6c 4e 75 e5 42 13 cb 2d 37 b4
     e9 c9 12 bc de d9 10 5d 42 be fd 59 d3 91 ad 38

  hash (0 octets):  (empty)

  info (18 octets):  00 20 0e 74 6c 73 31 33 20 66 69 6e 69 73 68 65
     64 00

  expanded (32 octets):  00 8d 3b 66 f8 16 ea 55 9f 96 b5 37 e8 85
     c3 1f c0 68 bf 49 2c 65 2f 01 f2 88 a1 d8 cd c1 9f c8

  finished (32 octets):  9b 9b 14 1d 90 63 37 fb d2 cb dc e7 1d f4
     de da 4a b4 2c 30 95 72 cb 7f ff ee 54 54 b7 8f 07 18

RFC8445 at page 71 says:
   finished_key =
       HKDF-Expand-Label(BaseKey, "finished", "", Hash.length)

   Structure of this message:

      struct {
          opaque verify_data[Hash.length];
      } Finished;

   The verify_data value is computed as follows:

      verify_data =
          HMAC(finished_key,
               Transcript-Hash(Handshake Context,
                               Certificate*, CertificateVerify*))

RFC8448 does not show how "finished" value is calculated. RFC8446 suggests, from a client prespective, that a hash is needed over the handshake, server Certificate and server Certificate Verify:
  verify_data =
      HMAC(finished_key,
           Transcript-Hash(Handshake Context,
                           Certificate*, CertificateVerify*))

My question is, these two encrypted messages, are decrypted first and then hashed, or the hash is done over raw encrypted data ?
Thank you.


texts: Geometric interpretation of an Edwards curve

texts:
Addition on an elliptic curve in Weierstrass form (over the rationals) is typically depicted with the following figure:

(Image CC SA 3.0 https://en.wikipedia.org/wiki/File:ECClines.svg)

To add two points, one draws the line that connects these points. The third intersection point is mirrored to get the result of the addition.

A curve in Edwards form might look like this:

(Image CC SA 3.0 https://commons.wikimedia.org/wiki/File:Edward-curves.svg)

However, the classical geometric interpretation for addition on Weierstrass curves does not seem to work on these Edwards curves.
Take for example the point $(0,-1)$. When doubled, this becomes $(0,1)$, the neutral point, according to the addition law $$(x_1, y_1) + (x_2, y_2) = \left(\frac{x_1y_2 + x_2y_1}{1-dx_1x_2y_1y_2}, \frac{y_1y_2 + x_1x_2}{1-dx_1x_2y_1y_2}\right).$$

When using the "classical" Weierstrass geometric interpretation (case 4 in the first image), I would become the point at infinity (which of course does not exist for an Edwards curve).

Clearly, Edwards curves follow a different way of life. Does there exist a similar geometric interpretation of the addition law for Edwards curves?


texts: How long would it take for a sha256 digest loop to reach the original hash or start cycling?

texts:
If I started with a sha256 hash such as

3f46fdad8e5d6e04e0612d262b3c03649f4224e04d209295ef7de7dc3ffd78a7

and rehashed it continuously (without salting):

i) What is the shortest time it would take before it started cycling in a loop or back onto the same value if at all?

ii) If it did cycle back on itself, could we assume that it had been cracked?

iii) How long would this take using modern GPU cracking techniques?

iv) If all the intermediary hashes were recorded in some kind of rainbow tables - presumably all the hashes within that cycle would be compromised?

v) What is to stop someone computing these cycles and offering cracks to sha256 hashes - likewise for other hashing protocols...

For Extra marks - What is the probability this question would be asked in this forum 60 billion years ago?


texts:
The question came up here, which left me thinking:

Is it possible to deduce the IV from CBC ciphered data, without knowing the key?
And if not, why is it considered a bad idea to create an IV by, for example, filename$\oplus$Key, if you never store the IV?

I know, that XOR is a no-go, when you are using ciphers, because, XOR is bidirectional. Having the filename and the IV will give me the key. But HOW will you get the IV from CBC ciphered data without having the key first?


texts: How do you create a large PRP from a small one?

texts:
How can you efficiently create a pseudorandom permutation with a large domain given a PRP with a small domain? Meaning: given an $n$-bit PRP, how can I create an $n k$-bit PRP?

I'm only interested in security up to $C 2^{\frac{n}{2}}$ messages, when $C$ is a reasonably-sized constant. For a power-of-2 $k$, the Luby-Rackoff construction essentially achieves this, although it requires $k^2$ calls to the PRF.


texts: Basic question about design of program with data encryption

texts:
I need to store encrypted files on a hard disk. The actual code side is not important for me now (I plan to use C# and AES-GCM encryption from Bouncy Castle library, please tell me if you think that's a bad idea!), but I'm having trouble designing the actual high-level algorithm.

How do I deal with user changing password (The key will be generated from password.)? Should I decrypt all the files encrypted with the old key and then encrypt them with the new one? Should I store the old password?

How to actually verify the password? An obvious answer that comes to my mind is "try to decrypt one of the files" but that doesn't seem right to me, because then there is no way to verify the password when encrypting the very first file. Sorry if these are dumb, but I'm completely new to cryptography.


texts: Server distributing/sharing a symmetric key to one or more clients via an established secure connection?

texts:
I have a server and a client device that share two separate data channels that each need to have authentication and encryption protections.
When a connection is made over data channel 1, it is secured using TLS where all data after handshaking is authenticated and encrypted using a single session key via AES-CCM.
Data channel 2 is completely separate one-way communication from server to client that is also to be authenticated and encrypted via AES-CCM. I would like to have the server generate the 2nd key and distribute it over the secure channel 1 connection.  Are there any defined protocols on how to do the distribution/sharing aspect of this?  Can I send the generated channel 2 key via the channel 1 connection without additional key wrapping or other mitigations?
I've seen some related posts but many were relatively old and it wasn't clear to me whether they were asking about the same thing I am.


texts: Does an IV need to be used in AES CTR mode?

texts: If I encrypt a message once using AES CTR, will I need an IV? Additionally, if I do use an IV, will I need to send it with the cipher text?


texts: Why a "Next Header" field is part of ESP trailer?

texts: Please explain are there any reason under the hood to place "Next Header" field in ESP trailer instead of ESP Header ?


texts: Is there value in performing signature during key exchange?

texts:
I looked around the net, however I couldn't see anything authoritative on this.

If one is using something like libsodium to perform key exchange (using x25519), is there value in using Ed25519/signature, to sign the public keys being exchanged for use in the key agreement scheme (assuming the ed25519 keys are correctly tied to an entities identity)?

Or is this over-engineering?

I have static keyPairs tied to user identity in my app, and see some value in signature despite the extra effort to sign public keys being exchanged during symmetric key agreement.


texts: what is SALSA20 Nonce and its requirements

texts:
what is the source of nonce in SALSA20 algorithm.
basically who provides the value of nonce in SALSA20 algorithm


texts: Is there a way to generate sound one-time pads out of public information?

texts:
Is there a way to 'mangle' a public data-source (for example, the current date  in YYYYMMDD or the top New York Times headline) to form a one-time pad that will sufficiently hide the pad's source?
What other issues would such a scheme be running into?

Disclaimer: I am not an expert cryptographer and am just interested in the matter - I do not intend to implement this cryptosystem.


texts: PKI Challenge Response: why is $h(r) = x$ enough to protect against chosen text attacks?

texts:
I think the question was asked somewhere else but not answered very precisely.

Quoting from the "Handbook of applied cryptography":

  Identification based on PK decryption and witness.
  Consider the following protocol:

  $A \leftarrow B:h(r),B,P_A(r,B) \quad (1)$

  $A \rightarrow B:r \quad \quad \quad \quad \quad \quad (2)$

  $B$ chooses a random $r$, computes the witness $x=h(r)$

  $P_A$ denotes the public-key encryption (e.g., RSA) algorithm of $A$

  The use of the witness $x = h(r)$ precludes chosen-text attacks.

Can anyone explain to me why this precludes chosen ciphertext attacks? If $h(x)$ is a simple hash, everyone can produce a different message, encrypt it with the public key, create the hash and send it to B. Of course B will response with a correct decryption so it can be used as decryption oracle.

I don't understand why $h(r)=x$ provides any additional value.