texts: Implications of Shor's algorithm on $F_{2^m}$ elliptic curves and GHASH

texts:
The security of elliptic curves depends on the difficulty of the discrete logarithm problem. Should Shor's Algorithm ever prove viable then elliptic curves would cease to offer any useful security properties, hence the need for post quantum crypto algorithms.

Most discussions of Shor's algorithm are for integers but how applicable is it for polynomials?

This is relevant because SEC2 defines a bunch of elliptic curves over $F_{2^m}$ instead of $F_P$.

I'm also curious about how Shor's Algorithm would impact GCM / GHASH, which operates in $F_{2^m}$.


texts: Determining average number of hash calls to get a hash that begins with X

texts:
I have been attempting to find an answer to a self-study question:

  If I have a hash algorithm that outputs 256 binary bits, on average, how many times would I have to call the hash function so that the output begins with 15 zeros?

I am absolutely lost, but bear with me here - each bit has two possible values and assuming an uniformly random output, there are $2^{256}$ (or 1.1579209e+77) possible outputs from the hash function.

So approximately, how many calls to the hash function ($H$) would be required to get an ouput value that begins with those 15 zeros?  Note that I am not looking for the probability of finding such a value (although that could be useful to know as well).


texts: need to develop CSPRNG. can i use ANSI X9.31 generator

texts: need to create secure PRNG. can i use ANSI X9.31 generator and modify its entropy rather using DT use something else >?


texts: 2 comparable hashes generated from one string

texts:
Assume a website where people log in with their password.

The password is now stored in sql database as:

md5(password + random_salt)

We are adding the possibility for clients to stay logged in and I am trying to find out the best way to do that.

Passwords should stay stored in the DB as hashes using some hash function (with the use of a generated salt) - first hash
When client logs in with his password, a different hash of his password should be generated (using the previously generated salt) and stored in the relation "second hash".
These two hashes should be comparable to each other, so that I could check if the second hash (generated during login) originates from the same string as the first one (generated during registration).

The second hash (the "login" one) would also be used to generate a key to encrypted sensitive user files (probably using AES, or is there a better option?).

I am quite new to this and I'm not sure if I am not being too naive, so I am asking. Is there a way to achieve this? Is there any source where I could read about these "comparable hashes"? I tried searching but I don't really know what to look for.


texts: Cracking linear congruential generator knowing a, b, m and scaled numbers

texts:
I was reading the book "Cryptographic engineering", one of the variation of linear congruential formula is as follow: $X_n = a_1X_{n-1} + a_2X_{n-2} \pmod {2^{31}-1}$

$a_1$ and $a_2$ are two prime numbers respectively

Given 50 scaled consecutive number $[s_{1}, s_{2}, ... s{50}]$, is there an efficient way to work backward?

If brute forcing is used, it will need to go through $2^{64}$ numbers.

What would be the efficient way to solve the formulas?


texts: Is the following non-interactive zero-knowledge set membership protocol provable secure?

texts:
Given the following Zero-knowledge set-membership protocol https://infoscience.epfl.ch/record/128718/files/CCS08.pdf]. That is given in the following steps (Please refer to page 9).

The Verifier

-select a set of elements denoted as $\phi$

-Select $x \in_{R} \mathbb{Z}_{p}$ and computes $y \leftarrow g^{x}$ and $A_{i} \leftarrow g^{\frac{1}{x+i}}$ for every $i \in \Phi$

The Prover

-select an element in the set $\phi$ denoted as $\sigma$

-Select $v \in_{R} \mathbb{Z}_{p}$ and computes $V \leftarrow A_{\sigma}^{v}$

-Select $s, t, m \in_{R} \mathbb{Z}_{p}$ and computes $a \leftarrow e(V, g)^{-s} e(g, g)^{t}$ and $D \leftarrow g^{s} h^{m}$

-computes challenge c using fiat-shamir heuristic as: $c=H(V\|a\| D)$

-computes $z_{\sigma} \leftarrow s-\sigma c, z_{v} \leftarrow t-v c,$ and $z_{r} \leftarrow m-r c$

-sends $C, c, a, D, Z_{\sigma}, Z_{v}, Z_{r}$ to the verifier

The verifier validates the proof by checking:

$D \stackrel{?}{=} C^{c} h^{z_{r}} g^{z_{\sigma}}$ and $a \stackrel{?}{=} e(V, y)^{c} \cdot e(V, g)^{-z_{\sigma}} \cdot e(g, g)^{z_{v}}$

Following, the following Theorem 1 (that proofs the zero-knowledge of the above protocol) as follows:

"the extraction property implies that for any prover P* that convinces V with probability ε, there exists an extractor which interacts with P* and outputs a witness (σ, r, v) with probability poly(ε). Moreover, if we assume that the extractor input consists of two transcripts, i.e.

$$
\left\{y,\left\{A_{i}\right\}, V, a, D, c, c^{\prime}, z_{\sigma}, z_{\sigma}^{\prime}, z_{v}, z_{v}^{\prime}, z_{r}, z_{r}^{\prime}\right\}
$$

the witness can be obtained by computing:
$$
\sigma=\frac{z_{\sigma}-z_{\sigma}^{\prime}}{c^{\prime}-c} ; \quad r=\frac{z_{r}-z_{r}^{\prime}}{c^{\prime}-c} ; \quad v=\frac{z_{v}-z_{v}^{\prime}}{c^{\prime}-c}
$$

The extractor succeeds when $\left(c^{\prime}-c\right) \text { is invertible in } \mathbb{Z}_{p}$"

My question:

Considering the ZKSM and proof given in the paper, if we consider the case where the following data

$${y,{A_i },V,a,D,c,Z_σ,Z_v,Z_r}$$
is made public (e.g., stored in public blockchain that acts the verifier). Thus, an adversary succeeds in getting the witness ($\sigma$, r, v) if he is able to obtain $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$. Is this case doable?. In other words, considering properties of fields
 can the adversary find $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$?.


texts: How to break an arbitrary XOR and Rotation based encryption?

texts:
I heard encryption based purely on XOR and Rotation is inherently weak. The paper Rotational Cryptanalysis of ARX says:

  It is also easy to prove that omitting addition or rotation is devastating, and such systems (XR and AX) can always be broken.

But I am not able to find any information on how to actually do it. Can anyone give a hint?

(Update:)

@CodesInChaos pointed out: "You can describe each output bit as the XOR of a fixed set of input/key bits. This results in a few hundred linear equations modulo $2$, which can be solved efficiently." For simple XR cipher, I understand how it works. But there are issues for me for more complex ones. Illustrated as follows:

Suppose a toy XOR/Rotation based cipher (cipher 1) which encrypts a 4 bit plaintext $P$ to a 4 bit ciphertext $C$ with a 4 bit key $K$. The encryption process is as follows (with example $p = 1001$, $k= 1000$, and $c = 1110$, all additions are modulo $2$ additions):

$E_1$. Right rotate $P$ by 2 bits, producing $M$ ($1001 \rightarrow 0110$),
$E_2$. XOR $M$ with $K$, producing $C$ ($0110 + 1000 = 1110$)

The corresponding decryption process:

$D_1$. XOR $C$ with $K$, producing $M$ ($1110 + 1000 = 0110$)
$D_2$. Left rotate $M$ by 2 bits, producing $P$ ($0110 \rightarrow 1001$)

Following @CodesInChaos 's advice, I can convert the decryption to the following linear equation system :

c1 + k1 = p3       1 + k1 = 1       k3 = 1
c0 + k0 = p2  ==>  0 + k0 = 0  ==>  k2 = 0          (A)
c3 + k3 = p1       1 + k3 = 0       k1 = 0
c2 + k2 = p0       1 + k2 = 1       k0 = 0

So far so good. But what if the rotation bits in the above step $E_2$ is not a constant 2, but changes with the input plaintext? For example, let's modify the above cipher a little bit to this (cipher 2):

$E_1$. Right rotate $P$ by $n$ bits, producing $M$. In which $n$ = the upper 2 bits of $P$ ($1001 \rightarrow 0110$),
$E_2$. XOR $M$ with $K$, producing $C$ ($0110 + 1000 = 1110$)

I cannot convert this cipher to a simple linear equation system. Because there is no longer a fixed function for each output bit as of key & input bits.

So my questions is: Is cipher 2 still qualified as a "pure XR" system? Is there still a generic way to break it?


texts:
I am new to cryptography and I am wondering Why is Proof of non-inclusion in a Merkle Tree harder than Proof of inclusion?

My naive thought for Proof of non-inclusion is that I would look for inclusion and if doesn't exist it is not included isn't it? I know this is wrong because I see papers on sparse Merkle trees etc but I couldn't figure out where my thought has a flaw? Can anyone explain preferably with less notation?


texts: how to mathematically prove a key exchange algorithm

texts: I want to know the basic methodology that can be used to prove that a key exchange algorithm is secure. I am not asking about any specific algorithm. I want to know what should be proven and how to prove in an abstract way.


texts: Very simple and minimal replay prevention scheme

texts:
Suppose a desktop client communicates with an internet server program via HTTP requests.

I have a symmetric secret key shared between them used for encrypting/securing communication between them.

I also mention that communication is almost one-way i.e almost always it is the client that sends some data to the server and server returns no data to the client except reporting unexpected errors like decryption failures. In my program the responses of the server aren't even (still) encrypted (although i can implement it relatively easily if really necessary - tell me the reason to do so) because the client makes no important action/decision upon receiving thease error responses (any response other than empty string is regarded as an error and is just ignored (at most printed/logged)).

My app is not very serious/security critical. It is just a little private program (and somewhat experimental/educational and I don't want to go further from a point in its security because I don't have enough reason/priority/time for implementing more details). So please don't be stringent about non-critical details. for example I know that the shared/master key shouldn't be used directly and each time a new session key should be generated somehow, but nonetheless i am using the master key directly for every encryption forever. My intended security is the bare minimum that is absolutely necessary so that ordinary hackers cannot misuse it or read my private data in transit, assuming the client and server environments are out of their reach.

So far i have implemented encryption (AES128(CBC)+HMAC-SHA256), but it seems to me that replay prevention is almost necessary too (and implementing it isn't much work and doesn't need much modifications to my existing codes). So i want to add replay prevention too, but in the most simple way possible for my app and its minimal security requirements.

I thought of a scheme like this:

Client stores a counter initially at 0
With each request this counter is incremented by one and sent along other data (counter is encrypted too or at least authenticated by MAC)
Obviously, server stores the last counter value(plus 1) it received and rejects every later request with a smaller counter value.
When client counter resets to zero again, e.g because of a reinstallation, thus it sends a request with an invalid counter to the server, server rejects and responds with an error message to the client and tells in this response the minimum counter value expected.
Client then sets the counter to the value reported by the server and sends the request again (Seems to me that the error response/counter value returned by the server doesn't even need to be encrypted/authenticated, because any other counter value will be rejected by the server again).

And, yes I am aware of the problem of counter variable reaching the end of its range (maximum) and reseting to 0. I will take care of it later (seems a simple problem to sovle)

Is this scheme correct in your opinion?


texts:
This is my first post on stack overflow/stack exchange so please excuse me if I asked the question in a bad way or the format is bad.
I am currently working through the cryptopals challenges and I got stuck on this one: https://cryptopals.com/sets/2/challenges/12 where you basically need to figure out a secret by extracting one byte a time exploiting AES-ECB (You are given a function which encrypts usertext + secret and encrypts it with AES-ECB). I understand why this attack works but what I don't understand is how we can extract more than one block size worth of bytes of the secret. Because let's say for block size = 8. We do the attack and discover the first eight bytes of secret, how can we get all the other bytes of secret as whatever amount of bytes we will enter now only parts of the first block size of secret will get discovered.


texts: Group Encryption or Multi-Party Encryption

texts:
I came accross a privacy and cofidentiality problem in medical field where patients medical record is available to certain doctors in full, but researchers/pharmacutical companies can only view the test reports but not the identity of the patient like name and social security number etc.

I know this can be implemented by some programming checks in application, but how to achieve this functionality using cryptography?
Where an encrypted record is partially decryptable by one party but fully decryptable by other.

Any guidance/reference to already published or in use scheme will be helpful.


texts: Understanding the length extension attack

texts:
I have been trying to understand exactly how a length extension attack works on SHA-1. I'll detail below what I've understood so far, so that I can convey my understanding of the same and hopefully get advice on where I'm going wrong.

Lets assume that for a message $m$, a secret $s$ is appended to it and the SHA-1 hash is calculated. If $\textrm{len}(m) + \textrm{len}(s)$ is not a multiple of the block size, a certain amount of padding is added to it to make it a multiple, and the hash is generated using what is essentially $s || m || \textrm{padding}$.

Now SHA-1 internally uses 5 registers — it takes in an block, generates new register values, turns the crank, takes in another block, generates new register values, turns the crank ... and so on till the end. When all blocks are exhausted, the register values are concatenated and spit out.

Assume that an attacker knows a certain value of $m$, for which he also knows the hashed key. In such a case, he knows the state of the 5 registers when $(s || m || \textrm{padding}$ was processed. Lets also assume that the attacker knows the length of $s$, so that he can predict how much padding was added.

Here is where I get confused. From what I've read so far, the attack involves taking the known hash, adding a certain amount of padding and then the value that we want. However, isn't the padding already used up in creating the hash? Why are we using padding in our attack?


texts:
I'm looking for a detailed explanation of the ciphersuites available in openssl.

openssl already offers the ciphers command which can be used to output, for example, the following:

$ openssl ciphers -v "HIGH,-SHA,-AES256"
DH-DSS-AES128-GCM-SHA256 TLSv1.2 Kx=DH/DSS   Au=DH   Enc=AESGCM(128) Mac=AEAD
DHE-DSS-AES128-GCM-SHA256 TLSv1.2 Kx=DH       Au=DSS  Enc=AESGCM(128) Mac=AEAD
DH-RSA-AES128-GCM-SHA256 TLSv1.2 Kx=DH/RSA   Au=DH   Enc=AESGCM(128) Mac=AEAD
DHE-RSA-AES128-GCM-SHA256 TLSv1.2 Kx=DH       Au=RSA  Enc=AESGCM(128) Mac=AEAD
DHE-RSA-AES128-SHA256   TLSv1.2 Kx=DH       Au=RSA  Enc=AES(128)  Mac=SHA256
DHE-DSS-AES128-SHA256   TLSv1.2 Kx=DH       Au=DSS  Enc=AES(128)  Mac=SHA256
DH-RSA-AES128-SHA256    TLSv1.2 Kx=DH/RSA   Au=DH   Enc=AES(128)  Mac=SHA256
DH-DSS-AES128-SHA256    TLSv1.2 Kx=DH/DSS   Au=DH   Enc=AES(128)  Mac=SHA256
ADH-AES128-GCM-SHA256   TLSv1.2 Kx=DH       Au=None Enc=AESGCM(128) Mac=AEAD
ADH-AES128-SHA256       TLSv1.2 Kx=DH       Au=None Enc=AES(128)  Mac=SHA256
AES128-GCM-SHA256       TLSv1.2 Kx=RSA      Au=RSA  Enc=AESGCM(128) Mac=AEAD
AES128-SHA256           TLSv1.2 Kx=RSA      Au=RSA  Enc=AES(128)  Mac=SHA256

It seems that ADH stands for "Anonymous Diffie-Hellman" but also implies specific groups and bit sizes.

I am interested in detailed explanations of what all the abbreviations are and generally which of these ciphersuites are considered secure.

Specifically:

What is ADH? Where is it standardized?
The listed MAC algorithms are hash functions. Is it using HMAC?
What does "Au" mean?


texts: Confused with the role of AES round keys

texts:
AES works when each plaintext block is arranged in a 4x4 array of bytes called states. State goes through 10 rounds of encryption consisting of 4 operations: bytesub, shiftrow, mix columns and add round key. I know how it all works but in preparation for my exam I have two  questions which I don't understand.

How will the algorithm be affected if the addroundkey wasnt used in any round? Also in another scenario where In each round, in the Add Round Key, instead of computing a bitwise XOR between the state and the key, what would happen if we use a bitwise OR?

My theory is that if the addroundkey wasn't used, then attackers can easily reverse the operations because the symmetric key isn't required.


texts: What's the preferable encryption for large data and files in terms of speed and security other than AES?

texts:
First of all, I'm relatively new to encryption so please bear with me.
I'm looking for a way to encrypt large amounts of data only on my device, no need to transfer my encrypted files/data (10-20GB or less), I don't really care about speed as long as the encryption is really strong. I have tried encryption with AES-GCM and using RSA for encrypting the AES Keys, but AES doesn't really give me that safety feeling like it's only 256bits maximum.


texts: About Cryptography in a Character Language

texts:
Suppose I had a message in Chinese (or another non-phonetic language) and I wanted to encipher it.

Some of the simplest encryptions in English are substitution ciphers, but such ciphers don't seem to be a viable option for a language such as chinese (it's more similar to a code...). What would be a simple cipher for such an alphabet? (Lets assume that we don't want to transliterate it to English first).

Second, suppose that someone had used a substitution cipher on such a language (in the code sense where every word stood for another).

Would frequency analysis still work?
Are non-phonetic languages more or less secure when used with substitution ciphers?
Assuming frequency analysis is not an option, how would one break it?


texts: What is difference between Unipartite Secret Construction, Bipartite Secret Construction and Multipartite Secret Construction

texts:
In this paper authors  extend Asmuth–Bloom and Kaya schemes to
bipartite access structures and further investigate how SSSs realizing multipartite access structures can be conducted with the CRT.

The authors, also, written  Secret Construction  procedure is same in    Unipartite  Secret Construction, Bipartite Secret Construction and Multipartite Secret Construction.

Unipartite(Asmuth–Bloom) Secret Construction

  Assume $C$ is a coalition of $t$ participants to construct the secret.
  Let $M_C =\prod_{i=1}^{C}m_i$  $y ≡ y_ i \mod m_ i $

  for $i ∈ C$, solve y in $GF(M_C  )$ uniquely using the CRT.   Compute
  the secret as
       K = y mod p

  According to the CRT, y can be determined uniquely in $GF(M_ C)$ .
  Since $y < M ≤ M_C$ , the solution is also unique in $GF(M)$.

Bipartite Secret Construction:

  Assume $C$ is a coalition of $\tau$ participants to construct the
  secret.  Let $M_C =\prod_{f(y_i) ∈  C}m_i$

  $y \equiv y_i \mod m_ i $

  for $f(y_i) ∈ C$, solve y in $GF(M_C  )$ uniquely using the CRT.
  Compute the secret as
        K = y mod p

Multipartite Secret Construction

  Assume $C$ is a coalition of $\tau$ participants to construct the
  secret. Let $M_C =\prod_{f(y_i) ∈  C}m_i$

  $y \equiv y_i \mod m_ i$

  for $f(y_i) ∈ C$, solve y in $GF(M_C)$ uniquely using the CRT.

  Compute the secret as
        K = y mod p

I am getting confusion regarding the difference between Unipartite Secret Construction, Bipartite Secret Construction and Multipartite Secret Construction to .

Could you please explain the intuitive difference between Unipartite Secret Construction, Bipartite Secret Construction, and Multipartite Secret Construction.


texts: Which test suit is better to say if PRNG is CSPRNG:TestU01 or NIST?

texts:
Actually my concern is that I am planning to apply xoshiro256+ for implementation of stream cipher https://prng.di.unimi.it/
for my cryptographic application. It passes the BigCrush tests. Will it provide me the same level of secuirty as any other cryptographically secure PRNG (CSPRNG)?
On the webiste, they claim that xoshiro256+ is a general purpose PRNG and not to be used for cryptography. But I still want to find out how far this PRNG is from being CSPRNG, may be a mathematical expression because my limitation is speed and this seems to be very fast PRNG and remember that it passes BigCrush.
My other question is that NIST statistical test suite https://www.nist.gov/publications/statistical-test-suite-random-and-pseudorandom-number-generators-cryptographic says that if a PRNG passes NIST tests then it is a CSPRNG. So how similar is BigCrush to NIST, again to know how far xoshiro256+ is from being CSPRNG?
P.S: I want to do a theoretical study of this issue as I am not well-versed in statistical testings practically on software.


texts: Computational requirements for breaking SHA-256?

texts:
Let's define "breaking" a hash function $H$ as being threefold (corresponding to the main properties of a cryptographic hash function):

preimage attacks to get $m$ knowing $H(m)$
second-preimage attacks to find some $m'\neq m$ knowing $m$ so that $H(m)=H(m')$
collision attacks to find $m_1,m_2\neq m_1$ for $H(m_1)=H(m_2)$

I wonder how much computational resources would in theory be required for performing each attack on SHA-256. I have little experience with complexity theory, but could not find much literature on this.

My approach was this: in general, there are $2^{256}$ possible hashes. Since there is no known structural weakness in SHA-2, brute-forcing a preimage is the only option and should take $2^{255}$ trials (half of the hash space). However most refer to $2^{256}$, is that because that means certain success rather than expected time needed?

A collision takes $2^{128}$ steps with a Birthday attack. I could not find figures for the second-preimage attack.

First of all, are my assumptions above correct? What would the complexity of the three attacks be?

I am also curious what "unit" a number like $2^{256}$ implies - is it something like floating-point operations that would be needed to run?

I am aware that SHA-256 is deemed secure given today's computational power. is it likely that increasing computer capacities (classical, not quantum computing) will become a threat to this over the next years?


texts: Is a 2 bit one time pad just as secure as a 128 bit one time pad?

texts: Obviously, it would be easier to stumble across the answer, but you still couldn't be sure it's correct. So it's still theoretically secure?


texts: What is the most common encoding of messages to polynomials?

texts: How polynomial based encryption schemes such as NTRU encode messages in to polynomials? Is there a generic conversion?


texts: Proof of knowledge outside of Zero Knowledge

texts:
Are there interesting protocols for which proof of knowledge is required, but not zero knowldege?

Is Proof of Knowledge an interesting proof by itself?


texts: A paper question about the security of hybrid encryption scheme

texts:
Why the decryptor can still use K to access the data even when K is updated?
QAQ


texts: What encryption mode should I use to protect a packet but the integrity of the entire packet, including its header, is protected?

texts: What encryption mode should I use to protect a packet, such that the payload of the packet is encrypted, but the integrity of the entire packet, including its header, is protected?


texts: Prime modulus for RSA and sharing a secret?

texts:
According to this paper entitled "Using Commutative Encryption to Share a Secret" they define their modulus to be a large prime p, which is public. Both exponents are private in this case.

According to the wikipedia article on RSA link the modulus has to be a product of two primes, and " p, q, and φ(n) must also be kept secret because they can be used to calculate d.", and the exponent can be public.

In the paper both the modulus (p) and φ(p) are known. How is the algorithm in the paper secure? Is it because both keys are private?

Is there a secure way for the same modulus to be used across all parties, and $a_i$ are public for each user?


texts: Is a 256 bit HMAC-SHA256 key compromised if the tail is used for identification?

texts:
Using a truncated hash of a key seems to be a safe way to identify the key (i.e. key fingerprint), but what about truncating a key itself in the case of HMAC-SHA256?

Example:

$ key=`openssl rand 32 -base64`
    $ keyId=`echo $key | cut -c 40-43`
$ echo $key
RlBDpvx3pCD/rs2SyeHX0enLOxCP7mEQCB8zvtQhD6g=
$ echo $keyId
hD6g
$

Is using $keyId as a way to identify the key secure?  I recognize that the security strength will be reduced, but is it a negligible/acceptable amount?  Is there something in the literature that addresses how disclosing the tail of a HMAC key impacts security?


texts:
My understanding of HOTP is that each password is unique and based on a counter.

$$PASSWORD = HOTP_1(K,C)$$

Where $C$ is an incremental counter.

What I wish to know, is how you keep the client and server in sync?  Looking at current systems (google authenticator), there appears to be no indication if the actual 'counter' number, but you can generate successive passwords at will.

What happens if, for example, the password you have generated uses $C = 5$, but the server is expecting $C = 3$?

Also, what is the 'integrity check' for?  Google cant seem to come up with a solution.


texts:
Are there encryption schemes with which it takes (significantly) longer to encrypt than to decrypt?

I am thinking of a specific situation in which a server continuously receives encrypted messages from different senders and has to decrypt each single one of them. To cope with the possibly large amount of messages the decryption process should be fast. However, to avoid that the senders send a large amount of automatized messages, the encryption process should take much longer.

Ideally, the time to encrypt a single message should still be acceptable, but it should become unfeasible to send a large amount of messages in a short time. The specific type of encryption does not matter and the server can be assumed to have all the necessary keys for the decryption of the messages (without the key, of course, the decryption process should take much much longer!).

In other words, sending a message should be "expensive", while receiving the message should be "cheap". Is there an encryption scheme that shifts the computational load to the side of the sender, so that it takes longer to encrypt than to decrypt a message?


texts:
Meet in the middle on 2DES uses $2^{56}$ memory.
Given the fact that the attacker has only $2^{45}$ memory.
How can the attacker adjust the attack so even with this memory limit, it will still be more efficient than looking after all the existing keys?

I guess you can separate this to a few lookups - a few tables - each time containing a different subset while making sure each row get compared. which should still be more efficient than $O(n^2)$. Is this the answer?


texts: Should the nonce passed to GCM be authenticated?

texts:
This answer recommends authenticating the IV with HMAC when using AES and then HMAC.

Since AES-GCM provides authentication too, should the external nonce passed to GCM be authenticated separately when passing over network? If not, why not? If it should be what is the recommended way to do it?


texts: How does using salt reduce rainbow table attack?

texts: I could create a rainbow table for a particular salt value and still create a successful attack similar to one without salt value.


texts:
I have a message and I want to verify its integrity and authenticity.

I have a shared secret (key) that is not used for other encryption.

Is it safe to send a plaintext message containing all the data I want, and to verify its integrity and authenticity using CBC-MAC?

I mean - of course the data is not secret, but do I have a risk of someone changing the message / MAC and messing with my message? Is it possible to deduct the Key?


texts: Question about using residue number system for repeated multiplications

texts:
I understand that when you are using RNS you need a co-prime moduli-set e.g. ${\{m_1, m_2, m_3\}}$, and the dynamic range is the product of each modulus in that set $M = m_1.m_2.m_3$. Also it's advantageous to select modulus values that are generalized mersenne numbers, so that operations in RNS are easier. And when you convert back out to an integer X you use the Chinese Remainder Theorem, something like this $ |X|_M=|\sum_{i=1}^n |r_iM_i^{-1}|_{m_i}M_i|_M$
(http://www.ccs.asia.edu.tw/ezfiles/2/1002/img/370/1203-3.pdf)

But the M / dynamic range would not necessarily be the prime you want to reduce by (for example the prime field in ECC), but all the papers I read don't really explain this, so not sure if it's something simple I'm missing or not?

For example say I have ${m_i}={2,3,5}$, this makes my $M=2.3.5=30$. So I start with value $X=7 = (1,1,2)$, do two squaring $(1,1,2)^2 = (1,1,4)^2 = (1,1,1)$, then convert out and I get $X=1$ (which is correct for $(7^2)^2$), but what if I wanted to do repeated squaring modulo a prime (e.g 23), is that possible?


texts: Is key derivation of a token shared secret necessary for usage of token in TOTP as specified by RF6238?

texts:
TL;DR: Is it necessary to generate a 'random' key from a shared token secret string before putting it into a TOTP algorithm that follows the RFC 6238 specification? Or is it okay for me to put the token secret directly into the TOTP algoritm (of course with proper base32 or hex format depending on the algorithm used)?

Long Version:

Hello, currently I am trying to solve a challenge that relates to me generating the correct 10-digit TOTP based on my userid and certain string combinations. However, currently I cannot seem to generate the correct output, even though I have followed the RFC 6238 specification correctly (as can be seen here: https://tools.ietf.org/html/rfc6238#section-1.2), and even borrowed the code provided in the RFC to generate the TOTP.

As some background, the task provider has given me a sample input and output like specified below:

Sample Input:

  Shared key: "ninja@example.comHDECHALLENGE003" (without double quotes)

  Hash function used: HMAC-SHA-512

  T0 = 0, Timestep = 30 seconds (as per specified in RFC6238)

  Expected TOTP of 10 digits

Sample Output:

  Successful TOTP generated: 1773133250, for time of Mon, 17 Mar 2014 15:20:51 GMT

  base64 encoded POST Authorization username/password request: bmluamFAZXhhbXBsZS5jb206MTc3MzEzMzI1MA==

  (I have decoded the sample POST authorization to be 'ninja@example.com:1773133250' hence why I can say that the sample TOTP output is 1773133250)

In an attempt to replicate this result, I inputted the shared key "ninja@example.comHDECHALLENGE003" into the totp algorithms that I used with a hex representation of the key, i.e. 6E696E6A61406578616D706C652E636F6D4844454348414C4C454E4745303033, especially for the TOTP algorithm that is shown in the RFC 6238. Unfortunately it seems that I cannot get the correct result and instead got the output like this:

Attempted input:

  Hex encoded seed for HMAC512: "6E696E6A61406578616D706C652E636F6D4844454348414C4C454E4745303033" + "6E696E6A61406578616D706C652E636F6D4844454348414C4C454E4745303033";

  Time inputted (the message that is going to be hashed) is 1395069651L, representing the time received in sample output

Result of attempt (same output from custom script, other Python modules, and the Java implementation given in RFC6238 documentation):

  Generated TOTP: 0490867067

After some more reading though, I have noticed that it seems that the token shared key/secret that is entered into the TOTP main function (i.e. the one that is going to be encoded into SHA-512) derived from a random generator or a key derivation function, according to the RFC 6238. With this in mind, my main question then would be (sorry after a long explanation haha):

Is it possible and actually necessary for me to first input the shared token to a key derivation function first, before then inputting it into the TOTP algorithm (i.e. do the Key Derivation first, then input into the SHA portion of the TOTP)? If so, should I then use the same shared key as he salt of the key derivation function?


texts: Why would we use a Key Agreement Protocol if we already have a key between 2 entities?

texts:
For example in my course there is this protocol :

Initialisation: A and B are sharing a symmetric key S.
(1) A -> B: Ra ; A generates a random number and sends it to A
(2) A <- B: Rb ; B does the same
A and B computes the session key K := E_S(Ra XOR Rb).

Why A and B would establish a new key K if they already have the key S ?
I don't get it.

For me, the Diffie-Hellman protocol is coherent because it establishes a key between 2 entities that have never talked before.


texts: Byte size of Diffie-Hellman public values

texts:
I have a scenario that uses RFC-3526's Diffie-Hellman Group 14 for 2048 bit key exchanges. From the document, it specifies the P (prime) value in hexadecimal value as:

  FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
  29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
  EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
  E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
  EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
  C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
  83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
  670C354E 4ABC9804 F1746C08 CA18217C 32905E46 2E36CE3B
  E39E772C 180E8603 9B2783A2 EC07A28F B5C55DF0 6F4C52C9
  DE2BCBF6 95581718 3995497C EA956AE5 15D22618 98FA0510
  15728E5A 8AACAA68 FFFFFFFF FFFFFFFF

It also specifies G (generator) as 2 which I assume in hexadecimal as:

  0x02

Assuming Alice's private key is a and Bob's private key is b. My question is when Alice and Bob exchanges their A and B where:

A = G^a mod P
B = G^b mod P

How big should I expect A and B to be in bytes?


texts: How does one attack a two-time pad (i.e. one time pad with key reuse)?

texts:
My question might appear the same as the question Taking advantage of one-time pad key reuse?, but actually I did read all the answers and none of them helped me with the details I need.

I am new to cryptography and my problem is with two time pad attacks on OTP.
The problem I had in my course was that I have 10 ciphertexts encrypted with the same key $K$. I am then given another ciphertext that I should decrypt.

I know that XOR-ing two ciphers gives me the XOR of their original messages.

My question is what is the correct thing to do after that?

I tried to take 3 ciphertexts $C_1, C_2$ and $C_3$.

Then get $S_1 = C_1 \oplus C_2  \oplus $' ', also get $S_2 = C_1 \oplus C_3 \oplus$ ' '.

After that I compared all corresponding characters in $S_1$ and $S_2$,
and if $S_1[i] = S_2[i]$ then I calculate $S_1[i] \oplus C_2[i]$ to get $K[i]$.

I tried this on paper before coding and it worked, but I might be missing something.

Is this the right approach? Why does it work?


texts:
This machine has the stator, with one half of the alphabet, and three rotors with replications of the other half in different order and repeated twice. There can have two rotors in use or the full three. There is only two types of strips, SMA and SMB. These are used to differentiate what strips are used in the encrypted message. Also, SMA strips can only be used with other SMA. Ditto with SMB strips. There are 3 strips for both rotors and stators. They are numbered 1 - 3. Is this machine relatively secure compared to other classical ciphers generated by a machine?

Key: SMA123/AQZ/2

Explanation: Using strips designated SMA, stator is SMA1, the first rotor is SMA2 and the second rotor is SMA3. The letters are representing the indicator letters, letters Q and Z below stator A. The two shows how many times the last rotor moves before the one above it does.

This machine is a quite primitive machine. It is basically a St. Cyr Slide with multiple moving strips (rotors). The rotors contain only one half of the alphabet. The stator, (the stable strip) contains the other half.

i.e.
Stator: 'ABCDEFGHIJKLM'

ROTORS CAN CONTAIN ANY PERMUTATION OF 'NOPQRSTUVWXYZ'

This property makes the cipher reciprocal making encryption and decryption easier.

As a note, this machine is NOT electrical. It is moving strips of plastic with the alphabet printed on them, held in place by staples on a board.

I can give further explaining if it needs be.


texts:
I need to use Pohlig-Hellman exponentiation cipher for reasons explained here. However, I can't seem to find an implementation of this cipher anywhere. It doesn't seem to be too difficult to implement from scratch - so, I want to try.

I do have the following questions:

How do I go about choosing primes? According to this, I should choose a large random prime such that (p−1)/2 is prime. But what algorithm should I use to do that? Also, is 2048 bits enough for my purposes (some context below)?
How do I go about choosing keys? I think these should be large random numbers, but how large? I would like to make the encryption as secure as with other more commonly used ciphers.

To give a bit more context: I would be encrypting relatively small messages. Vast majority of my messages will be under 32 bytes, and no message will be larger than 64 bytes. I will be padding and scrambling messages using salts before encrypting them to avoid deterministic output.


texts: Where can I find open source code for Encryption Switching Protocol?

texts:
The concept of Encryption Switching Protocols was introduced in CRYPTO.

I was wondering if there is any pseudo-implementation of the protocol available or can I get some insights on how to implement it?


texts: Fisher Yates on "faulted" random number generator cryptanalysis

texts:
For the sake of curiosity and fun, i have implemented a C# program that operate as deck dealer on 40 cards deck (following the Fisher Yates shuffeling algorithm https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle).
The fun part is that i have used the "faulted" rng that the language provide (small seed compared to cards permutation space and not cryptogaphically secure) and now i am trying to figure out how to write a program that can infer deck permutation only seeing a small fraction (a fifth) of the generation.
So in my scenario, deck dealer program shuffle 40 cards and assign them at each round to one of the 5 player.
How can i recostruct the permutation if i see only one player cards? i need some hint here (because seems to me that the shuffling procedure hide a lot of the problem in the pseudo random number generator, so i have no idea how to exploit the problem of that generator and seed).
I would premise that i am not a expert on cryptanalysis, just an entusiast
Here the program i wrote :
class Program
{
    private static Random _rng = new Random();

    static void Main(string[] args)
    {

        for( int i = 0; i < 10; i++)
        {
            Program.ShuffelingAlgorithm();
            Console.WriteLine("\r\n\r\n");
        }
        Console.ReadKey();
    }

    private static void ShuffelingAlgorithm ()
    {
        List<int>[] players = { new List<int>(), new List<int>(), new List<int>(), new List<int>(), new List<int>() };
        int[] cards = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39 };

        for (int i = 39; i >= 0; i--)
        {
            int next = _rng.Next(0, i);

            int choosen = cards[next];
            players[i % 5].Add(choosen);

            cards[next] = cards[i];
        }

        foreach (var player in players)
        {
            foreach (int card in player)
                Console.Write(card + "\t");

            Console.WriteLine();
        }
    }
}


texts: How to encrypt data with the Threefish cipher

texts: I want to know how the Threefish cipher can be used to encrypt and decrypt. I tried to find out by searching the Internet but can't find a concrete answer. The only answers are theoretical in nature which is not usable to me.


texts: Chosen Plaintext attack on AES in ECB mode

texts:
I am familiar with the following method for an chosen-plaintext injection attack on ECB ciphers, where I am allowed to append a block of bytes to the packet being encrypted:

I inject a string with known bytes one less than the blocksize and try figuring out what the first byte of the available data could have been by brute forcing all the 256 possiblities. And then, I carry this information over to extract the next byte.

I can understand why this could be used to extract a blocksize worth of the original plaintext. However, how do I extend this method to get bytes beyond the blocksize?


texts: Can Verifiable Random Functions be used to pick a random node from a pool?

texts: Let's say that I have a decentralized system and I have a list of nodes published on a public log like a blockchain. I want a node A to be able to connect to another node B. B should be chosen randomly from a subset S of the list of all nodes. Once B is chosen I want the other nodes in the system to verify whether B was actually chosen randomly. We can assume that every node is able to compute S so my question is: Can A use a verifiable random function to choose a node from S which we call B and have all the other nodes be able to verify that the node B I chose was the node that was supposed to be chosen?


texts: Inverse function of RSA and safe prime requirement of DH Key exchange

texts:
Ok so the inverse function of RSA encryption (that is decryption) is
$ m \gets c^{d}\bmod N$ where $d$ is the secret exponent
As I understand the hardness of RSA depends on two things: the Integer factorization problem and the discrete logarithm problem. While studying DH Key Exchange, it is a requirement that a safe prime is chosen that will serve as the modulus. But the decryption function of RSA already has a non prime modulus. How come RSA cannot be broken with the modulus not being prime, let alone a safe prime? And what is wrong with choosing a multiple of two primes as modulus in DH Key exchange?


texts: Parameterizing adversaries with security parameters

texts:
In many cryptographic games, the adversary doesn't seem to be parameterized by the security parameter.‡ Are such games equivalent to variants in which the adversary is parameterized by the security parameter?‡‡

‡ E.g., Bellare et al.'s IND-CPA (Crypto'98) defines: $(pk,sk) \leftarrow K(1^k)$; $(x_0,x_1,s) \leftarrow A_1(pk); ...$, i.e., $A_1$ isn't taking $1^k$.

‡‡ E.g., is the game above equivalent to: $(pk,sk) \leftarrow K(1^k)$; $(x_0,x_1,s) \leftarrow A_1(pk,1^k); ...$.


texts: What language classes beyond NP allow constant-round zero-knowledge proofs?

texts:
While discussing proving a language in $\Sigma_2$ from a client to a server with a friend we realized that while we know that such a language is provable in zero-knowledge, we didn't know whether it was provable in non-interactive zero-knowledge. This then led us to find this answer which states it is sufficient for a zero-knowledge proof to be constant-round to be transformable into a non-interactive one via Fiat-Shamir.
This then led me to confirm that in fact NP allows constant-round zero-knowledge proofs (PDF), which of course lead to the question in the title.
So:
Which language classes that include P allow constant-round zero-knowledge proofs - other than P and NP - and for which do we know that every zero-knowledge proof needs to have non-constant number of rounds?


texts: Hash for use in embedded HMAC application

texts:
I developed a GNSS logger (http://flysight.ca) which has become popular for scoring skydiving competitions. At the moment, there is little protection against competitors falsifying tracks, but I would like to change that.

The device uses an 8-bit AVR microcontroller. Memory and clock cycles are extremely limited. Because of the hardware design, the device has no warning when it is being turned off. This means it is not possible, e.g., to perform a computationally intensive signature only when the log file is closed.

The competition occurs over a few days. There is a central PC-based scoring system which is used to initialize and read data from the GNSS loggers.

Given these conditions, what I have in mind is the following:

The scoring system generates a unique random key at the start of the event.
Each GNSS logger is initialized with this key, which can be stored securely.
When a row is written to the log file, a cumulative signature is computed using an HMAC based on the key generated in (1).

Alas, even MD5 exceeds the resources I have available, so I am wondering if the modest security requirements (in particular, that signatures need only be secure for a few days) might allow me to use a faster hash function.

If you have a different idea, I'd love to hear that, too. Thanks so much for your help!


texts: Can curve25519 keys be used with ed25519 keys?

texts:
Can curve25519 keys be used with ed25519?

I'd prefer to use ed25519, but there isn't a fast java version.  For my application, I'd like to use curve25519 until I can get a faster ed25519 for java.

At the very least can the curve25519 keys be restricted if some can be converted ed25519?


texts: Why are key lengths in asymmetric algorithms typically longer than key lengths in symmetric algorithms?

texts:
Apologies if this is a duplicate question.  I did search prior to posting :-) I think it may be somewhat related to my other question here but I think it's different enough to warrant a separate question page.

Symmetric algorithm key lengths seem typically smaller to me:

AES uses keys sizes of 128 bits, 192, or 256 bits.
Triple DES uses 168-bit keys
Etc etc. etc.

Conversely, assymetric algorithms seem to require much larger keys:

RSA uses variable length keys between 1024 and 4096 bits.

Why is this?  What about asymmetric cryptography requires the significant jump in key sizes?


texts: How can I simulate and measure brute force hacking using RSA?

texts: I want to implement brute force hacking using RSA. How can I simulate and measure time duration? What software (or software-based simulator) would be needed?


texts: what does differential privacy (in machine learning) promise or guarantee?

texts:
I am recently reading some papers about privacy-preserving machine learning.

Some works incorporate the idea of differential privacy to protect the privacy of the training dataset when the model is published. The basic framework is as follows:

A trusted party (call it TP) possesses the training dataset in cleartext. TP then conducts some machine learning task and produces a prediction model. In the training process, TP will add some noise to the parameters (details omitted) such that the resulting model is noisy but is still accurate enough. It is then theoretically proved that some notion of differential privacy is achieved.

Meanwhile, I am aware of some "model inversion attacks" that can recover the training records given only a particular label and black-box access to the model.

So, what does differential privacy promise or guarantee in the context of privacy-preserving machine learning?

Specifically, suppose I am the owner of one record in the training dataset. The TP published a noisy model and tells me that it has $\epsilon$-privacy and the publication of the model will not violate my privacy. So what does it mean? Because I know that some model inversion attacks can recover my record. Does this violate the $\epsilon$-privacy?


texts: is there a problem with the following private set intersection protocol

texts:
Say Alice has the following set:  $\{A_1,A_2,\ldots,An\}$
and Bob has the following set:  $\{B_1,B_2,\ldots,B_m\}$

Alice creates a key $a$ and bob creates a key $b$
these keys should be commutative (eg: use RSA)

Alice encrypts each element of her set with $a$ to create $\{A_{1'},A_{2'}, \ldots,A_{n'}\}$
and similarly Bob makes $\{B_{1'},B_{2'},\ldots,B_{m'}\}$ with $b$

Alice sends her set to Bob and Bob sends his to Alice.
Alice encrypts each element of $\{B_{1'},B_{2'},\ldots,B_{m'}\}$ with a to make $\{B_{1"},B_{2"},\ldots,B_{m"}\}$ and similarly Bob makes $\{A_{1"},A_{2"},\ldots,A_{n"}\}$

Now Alice sends $\{B_{1"},B_{2"},\ldots,B_{m"}\}$ to Bob and Bob sends $\{A_{1"},A_{2"},\ldots,A_{n"}\}$ to Alice.

Because the keys commute, if $Bi=Aj$ for some $i$ and $j$, then $Bi" = Aj"$
Thus Alice and Bob can each identify which elements they have in common.

Also this protocol only requires encrypting and communicating each element twice so it has $O(n+m)$ run time.

I have not been able to find this protocol anywhere and it seems very simple so I thought there must be a problem with it.


texts: Encrypt-then-HMAC with a single key is secure?

texts:
The partition oracle attacks exploits the non-committing AEAD schemes.
Informally, a committing encryption scheme is one for which it is computationally intractable to find a pair of keys and a ciphertext that decrypts under both keys. AES-GCM and ChaCha20-1305 fail on this so they are non-committing.
As a countermeasure to the partition oracles, it is advised to use  Encrypt-then-HMAC with one key since HMAC is committing. I.e. the key for encryption and HMAC are the same. Normally, we don't advise using a key for two different purposes. This, however, advised in the paper.
This question is specific to HMAC. Is there any published attack on a scheme that uses the same key for encryption and HMAC? Or any article that shows its security exists?


texts: What is the Common Reference String (CRS) model

texts:
I came across the notion of Common Reference String (CRS) model while reading this paper on a protocol for UC Oblivious Transfer: https://eprint.iacr.org/2007/348.pdf

I did some research and it seems to me that the CRS model is just some way to model hash functions: What are alternatives to the random oracle model for modelling hash functions?

My questions are:

What is exactly the CRS model?
What are the main differences, comparing to the Random Oracle Model (ROM)?
What are the advantages and disadvantages of using the CRS model instead of using the ROM?

Thank you in advance


texts: FHE over the Integers - reduction to approximate gcd problem

texts:
I have three quick questions concerning the reduction of the scheme to the approximate gcd problem:

What exactly do the authors mean by $q_p(z_1')$ being the odd part of the gcd? (last line of step 3)
In step 4 (recovering p): Where does the $\pi^2/6$ come from? I'm guessing it has something to do with prime distributions, but I couldn't find anything on google. Also, $\pi^2/6 \approx 1.6 $  and not $0.6$, so is the formula wrong?
Thanks @Thomas, found it on wikipedia: The probability that two random numbers are relatively prime is $1/\zeta(2) = 6/\pi^2 \approx 0.6$, so the paper just has nominator and denominator switched.
Also in step 4: Am I correct that $\overset{\sim}{z} = z_1'$, i.e. the non-zero output of the first round of the binary gcd algorithm?

Link to the paper: https://eprint.iacr.org/2009/616.pdf

I'm referring to section 4.1.


texts: How to Sample from Frobenius Eigenspace?

texts:
So I was implementing the $2$-point method described here[1], which requires to samples two points $P_0, P_1$ in the Frobenius eigenspace initially. It uses a method called Elligator, which seems to me only samples $\mathbb F_p$ rational points.

Suppose one is given a supersingular curve $E$ defined over $\mathbb F_p$ with Elkies prime $\ell$. Since the $\ell$-torsion $E[\ell]$ is a $\mathbb F_\ell$-linear space of rank 2 and the Frobenius mapping $\pi$ is linear. Let $\lambda$ be one of the eigenvalue in $\mathbb F_\ell$. How would one sample from its corresponding eigenspace $E[\pi-\lambda]$?

For $\lambda=1$ we simply take $\mathbb F_p$-rational points, but what about cases where $\lambda \neq 1$, say $\lambda=-1$?

[1]"A Faster Constant-time Algorithm of CSIDH keeping Two Points," page 10, Algorithm 3.


texts: Is succinct verification of an arbitrary data transformation theoretically possible? Is it feasible? How?

texts:
Given input string S, and transformation (i.e. computer program) T, is it possible to provide a succinct proof that another binary string S' is identical to the output T(S)?

By "succinct", I basically mean significantly less computationally intensive than repeating the original transformation. Also, I am ok with limiting the operations that can be performed by T to a specific set, but ideally this set should be Turing-complete.

I am encouraged by what I have read about zk-SNARKs that this type of thing is at least within the realm of the conceivable, but much of the underlying cryptography is currently unfamiliar territory to me, and it is not clear whether this type of proof is something I can use in my code, how much effort this would take, and how much compute power would be necessary for sizable input data sets.

Ideally, I'd like to leverage a reasonably friendly API to a well-written cryptographic library, but I am also willing to do a fair amount of the grunt work and open-source what I come up with.

Direct answers, as well as any helpful resources, will be much appreciated.


texts: Building a 4-bit S-box with a 4-uniform DDT

texts:
I am looking for a 4-bit S-box which has only 4s in its difference distribution table (except the top left corner) but I was not able to find one in the literature.
Has such an S-box been already published? If not, is it theoretically possible to reach this property? If so, how to proceed?


texts: Is it okay to have no IV when using AES-CBC with unique keys, that are however derived from one shared key?

texts:
Given $\operatorname{AES-CBC}$ (128-bit), with $IV=0$  and unique encryption keys $$K_{Enc} = \operatorname{CMAC}(MK, \text{known_text})$$ where $MK$ is a shared symmetric 128-bit key and $\text{known_text}$ would be some concatenation of a message counter and a device ID, that are transmitted in plain text. $K_{Enc}$ are by themselves unique keys, however, the CMAC algorithm and $\text{known_text}$ are known to the attacker. This answer says that if the first CBC block is known plaintext, the complexity of finding one unique key reduces by $n$, the number of intercepted messages (with unique keys).

In this case, does this only make finding $K_{Enc}$ easier, or is $MK$ affected in the same way?

Additionally, if $MK$ is also affected, is an attack with only the factor $n$ relevant?

Considering there are $2^{128}$ possibilities for $MK$, wouldn't n have to be ridiculously large to make computing $MK$ feasible?


texts: How to compute the dataset size required by dieharder tests?

texts:
I am trying to use the dieharder random number test suite.
However, this suite requires massive amount of data (this paper claims 228GB for no rewinding for every test) for most of the tests. I'd like to understand how rewinding is implemented and to know how much data is required for each test. It seems related to the tsamples value but I cannot find an exact correlation.
For example, if I generate 400MiB of data using dd if=/dev/urandom of=random.dat bs=1M count=400, this produces the following (cropped) output:
$ dieharder -a -g 201 -f random.dat
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
 file_input_raw|                      random.dat|  6.38e+07  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.70238534|  PASSED
# The file file_input_raw was rewound 1 times
      diehard_operm5|   0|   1000000|     100|0.74169241|  PASSED
# The file file_input_raw was rewound 2 times
  diehard_rank_32x32|   0|     40000|     100|0.03164866|  PASSED
# The file file_input_raw was rewound 2 times
    diehard_rank_6x8|   0|    100000|     100|0.18168084|  PASSED
# The file file_input_raw was rewound 3 times
   diehard_bitstream|   0|   2097152|     100|0.59056568|  PASSED
# The file file_input_raw was rewound 5 times
        diehard_opso|   0|   2097152|     100|0.19175240|  PASSED
# The file file_input_raw was rewound 6 times
        diehard_oqso|   0|   2097152|     100|0.67542036|  PASSED
# The file file_input_raw was rewound 7 times
         diehard_dna|   0|   2097152|     100|0.04906220|  PASSED
# The file file_input_raw was rewound 7 times
diehard_count_1s_str|   0|    256000|     100|0.80349572|  PASSED
# The file file_input_raw was rewound 8 times
diehard_count_1s_byt|   0|    256000|     100|0.43003125|  PASSED
# The file file_input_raw was rewound 8 times
 diehard_parking_lot|   0|     12000|     100|0.07270933|  PASSED
# The file file_input_raw was rewound 8 times
    diehard_2dsphere|   2|      8000|     100|0.92548415|  PASSED

I assume that dieharder just loops over the file, keeping its pointer position when jumping to the next test and that The file file_input_raw was rewound N times is just the total count that the pointer reached the end of the file.


texts:
I recently started learning about Hash Functions for my first time, and I've gone through and have tried to understand the SHA1 process.

Brilliant does an excellent job of explaining it step by step.

https://brilliant.org/wiki/secure-hashing-algorithms/

As far as I've understood, hash functions are meant to be collision-resistant and really hard to back-calculate, even if one knows the exact process.

Although I can see the process, to me who doesn't know much about cryptography yet, the process seems extremely random - as if a drunk person was asked to perform mathematical operations on a bunch of bits.

I can't really see the motivation for the precise steps taken in SHA 1...

What about those steps make it collision resistant?
What makes it hard to "back-calculate"?
Why is the process...what it is? Why not some other "random mathematical operations"?


texts: Why must the sender and receiver be synchronised in synchronous stream ciphers?

texts:
I would like to know why the sender and receiver must be synchronized in synchronous stream ciphers as said in synchronous stream cipher. Why is there no synchronization between the sender and receiver in asynchronous stream ciphers?

I'm thinking that a plain text is first encrypted and then decrypted. I can't get how encryption and decryption are done at the same time. Is this synchronization done in block ciphers too?


texts: Backdoor Designer Key Recovery in LowMC-M

texts:
The paper https://eprint.iacr.org/2020/986.pdf proposed a framework for embedding a malicious backdoor in LowMC cipher, that will later help the designer to recover the secret key in the known-plaintext attack setting.
As the framework is scalable, suppose a cipher with 16 bit block size of 3 rounds is constructed. The framework generates the necessary constant parameters (RC, key matrices, linear layer matrices etc.) for designing a cipher along with deterministic differential characteristics for key recovery. For the above setting with 2 differential characteristics embedded, it generates  as
How the designer knowing the tweak pairs and the Plaintext differences can be able to recover the key in a short span of time in contrast to an attacker not knowing any of these parameters.
How the key can be recovered using plain differential cryptanalysis in this setting, I am confused or not getting the elaboration presented on page 17 and page 19? Will the designer be able to recover the round keys or the main key being input to cipher?
According to the article, only one differential characteristics (tweak pair) is able to recover the key, but for enhanced security more should be embedded? How one differential characteristics (tweak pair) embedded over r-1 round will be able to recover the key?


texts:
According to the pseudocode, keys longer than the block-size of the underlying hash function are shortened by hashing the key. Furthermore, keys shorter than the blocksize are zero-padded up the length of the block-size.

    if (length(key) > blocksize) {
        key = hash(key) // keys longer than blocksize are shortened
    }
    if (length(key) < blocksize) {
        // keys shorter than blocksize are zero-padded (where ∥ is concatenation)
        key = key ∥ [0x00 * (blocksize - length(key))] // Where * is repetition.
    }

Taking into account that the block-size of SHA3-512 is 72 bytes, and it's output is 64 bytes, does that mean the keys longer than 72 bytes should first be hashed and then the resulting 64 bytes should be zero-padded?


texts: Wikipedia pseudo code is unclear about how to pad SHA-512

texts:
In Wikipedia pseudo code of SHA-512 the padding section says pad 1 bit then 0 bits. It then goes on to say append length without 1 or 0 padding. What does that mean?

https://en.wikipedia.org/wiki/SHA-2#Pseudocode

  append length of message (without the '1' bit or padding), in bits, as 64-bit big-endian integer

The appending of message length in sha-2 as a 64 bit integer without 1 and 0 padding is a bit confusing. How is it different from SHA-1?


texts: What is the effect of the different AES key lengths?

texts:
How does a changing key length affects the ciphertext, not only in case of AES, but in general? I know that the key spaces become much larger and the number of rounds in case of AES changes, but is security really that much enhanced that if I choose 256 bits as key length it is sort of unbreakable?

Something else what I'm thinking about currently, any idea if it is possible to get any details about key length or algorithm of an observed ciphertext? For example when measuring the entropy (or anything else) is there any difference e.g. between AES and DES?


texts: What exactly is the contents of the LDAP userSMIMECertificate attribute

texts:
I am hoping someone can help me get past what has seemed to be a small step that has taken months with no resolve. Specifically: I still do not seem to be able to come up with what exactly are the actual bits on the wire for userSMIMECertificate to allow Outlook clients to send an encrypted s/mime email. Maybe I could get a pcap dump of an unencrypted LDAP exchange that has a userSMIMECertificate that an Outlook client used to successfully send an encrypted S/MIME email? OR Alternatively an exact example of the hexadecimal string pasted into the Active Directory Users and Computer-> user Properties->Attribute Editor->userSMIMECertificate->Edit->Add->Value field that made Outlook clients happy?
I have had no problem when using the userCertificate attribute, filling it with a hex encoded DER end certificate (openssl x509 -in cert.pem -outform der | xxd -p > cert.hex Then cut and paste the ascii hex into the AD Attribute editor). But most s/mime certs require an intermediate certificate to chain thru, so this does not work. I have tried every encoding variation I can imagine of pkcs7/cms blobs* (pem->hex, smime->hex, der->hex,...) but Outlook clients still pop-up the "...missing or invalid..." certificates message if I use userSMIMECertificate instead of userCertificate. Turned on Outlook debugging but not a peep wrt this error. So I have no idea what the problem is. Have wireshark but it does not decode the userSMIMECertificate attribute. Is there some magical OIDs or SEQUENCE OF or CONTENT OF elements I need to add. I do have code to create any ASN/DER packets to return on port 389. It isnt BER is it? As you can see I am desperate.
Any help appreciated.Thank You
*Following the excellent example provided in a similarly named question and then trying every encoding, eg., raw smime into hex and paste into AD; use openssl pkcs7/cms to convert into DER, PEM, p7s, p7m, ...  I put a sample file here https://www.co.tt/userSMIMECertificate.html


texts:
Ed25519 signatures consist of $(R, s)$, where $s = r + H(RAM)a$ $mod$ $l$, and $R = rB$. This differs from the Schnorr signature where instead of $R$, the signature contains the hash $h=H(RAM)$. According to the Elligator paper (page 5) "one can reconstruct $(h, s)$ from $(R, s)$ and vice versa".

I see that $(R, s) => (h, s)$ is trivial, but how would one derive $(R, s)$ from $(h, s)$?

Or more generally, how would the verification equation look like with $(h, s)$ as the signature?

(Motivation: I'd like to use $(h, s)$ as the signature to get indistinguishability from random numbers without needing the Elligator 2 map. Probably means no bulk verification, but that's not needed for what I'm thinking about.)


texts: Cryptocurrency serving as hash breaking?

texts:
There are many people mining for Bitcoin right this second.[Citation needed]

Bitcoin's proof-of-work mining system is based on a hash function (SHA-256, I believe), and there are ASICs built specifically for mining this.

Would it be possible to engineer a cryptocurrency such that the calculations of the mining process could be used to break hashed passwords? Without the miners knowing?

And, assuming a worldwide mining community approximately equivalent to Bitcoin's and with dedicated hardware for the purpose, would this be a feasible way of breaking hashed passwords?


texts: Explaining Berlekamp-Massey Algorithm in simple/layman term?

texts:
My foundation in Mathematics is not great. But I would like to understand how Berlekamp-Massey Algorithm works and how it is used in lay-man terms.

The only thing I find out there is the emphasis on discrepancy and how to make it zero (which means no discrepancy), and it is used to determine the minimal polynomial factor to produce sequence of bits.

The resources out there are full of mathematical equations which I do not understand, and to be honest, I don't know where to start. But I don't want to give up.

I'll appreciate any resources or books which are simple enough for a young student.


texts:
I have to find a solution to this problem: I have a network composed by 1 server and some client. The server has a couple of keys (public and private) and it shares a secret key with each client. My goal is to exchange a session key between the server and the clients.

I've evaluated some solutions, but I am unsure if my reasoning is correct.

I started thinking about DH, looking for a solution making it secure. And then I realised that maybe the client could randomly generate the session key and then it could send the key to the server in a secure way. In particular, my “secure way” consists in calculating the MAC of the session key using the shared secret key between client and server, and then encrypting $(MAC || session key)$ with the server's public key. In my opinion this “protocol” provides confidentiality, integrity and a sort of authentication using the secret shared key.

To conclude the protocol the server should send an ACK if the exchange has worked.

To recap:

Client:

generate $k$ // random session key
$t \leftarrow M(k,s)$ // calculate MAC using s(shared secret key)
$c \leftarrow E(es , k||t)$ // Encrypt $k||t$ using server's public key
Send $c$

Server:

$k||t \leftarrow D(ds , c)$ // Decrypt c using server's private key
$t´ \leftarrow M(k,s)$
$(t == t´)$ ? OK : ERR

I'd like to know if my reasoning is correct.


texts: security in format preserving encryption

texts: In format preserving encryption an attacker knows the format and data type of the plain text. The format of the plain text and cipher text are same. usually cipher text are unreadable form. then how FPE is secure?what are all the possible attacks on FPE cipher?


texts: How are these AES MixColumn multiplication tables calculated?

texts:
I'm using the mul2, mul3, mul9, mul11, mul13 and mul14 tables for the MixColumn and InvMixColumn steps in AES-128. However, I got these off some Github repository, and now I'm looking for an actual source explaining how these were calculated and so on.

I cannot find anything proper on Google, can anyone help me out?


texts: Can we use Pohlig-Hellman Exponentiation Cipher with a PRG to achieve an oblivious PRF

texts:
The Commutative Cipher Setup

Alice and Bob agree on a 2048-bit safe-prime $p$, where $(p-1)/2$ is also a prime.
Both parties have an encryption exponent $e$ in the range $(1, p-1)$ with $gcd(e, p-1) = 1$. And a decryption exponent $d$ chosen such that $d * e ≡ 1\bmod (p-1)$. Alice has $(e_A, d_A)$ and Bob has $(e_B, d_B)$ as their private key pairs.

Note:
I've also discovered that @fgrieu has proposed two variants of Pohlig-Hellman adressing some of the problems of modular exponentiation. Please assume the the key generation is done according to their explanation in both. variant 1, variant 2
We expect, this commutative cipher setup should be secure enough to use.

The Protocol
Alice has a message $m$ and wants to perform an oblivious PRF with Bob for this message.
The steps are as follows:

Alice seeds a PRG with $m$ and generates a 2048 (or 2047) bit random output $r$
a. For the properties $r$ satisfies, please check the PH variant by @fgrieu

Alice calculates the following encrypted random sequence with modular exponentiation, $E_A(r) = r^{e_A} \bmod p$ and sends the result to Bob.

Bob calculates $E_B(E_A(r)) = (E_A(r))^{e_B}\bmod p = E_{A,B}(r)$ and sends the result $E_{A,B}(r)$ back to Alice

Finally Alice calculates $D_A(E_{A,B}(r))=(E_{A,B}(r))^{d_A}\bmod p = E_B(r)$.

This should be the same value, where Bob:

Seeds the same PRG with the message $m$ to get $r$ (The same sequence Alice got from her PRG)
And calculate $E_B(r) = r^{e_B}\bmod p$

I believe this protocol should be satisfying the requirements of an Oblivious PRF. I'm assuming, given a random input, we can use modular exponentiation as a PRF.  Using the commutative nature of modular exponentiation, I believe we can achieve an Oblivious PRF. However I'm not sure if that's true, and I don't know how to prove this.
Once Alice and Bob have achieved an Oblivious PRF, My final goal for this OPRF is to use it for a Private Set Intersection protocol. Based on the answer of @Mikero in the question: How can Alice enable Bob to look-up values in a private map
Do you see any vulnerabilities here whether it might leak the keys of either parties or the message of Alice? Do you see any problems with my assumptions and utilization of modular exponentiation, if there are any points potentially insecure and should be avoided or fixed?


texts: How to handle the extra 12451 elements in Sophie-Germain Counter Mode?

texts:
In Sophie-Germain Counter Mode (SGCM), the $GF(2^{128})$ field multiplication of Galois Counter Mode (GCM) is replaced with normal multiplication $\bmod 2^{128}+12451$.  Because the block size is 128 bits, the extra 12451 elements of the group do not fit in the output.

The SGCM defining document says the following about the extra elements:

  Should the value be equal to $2^{128}$ or larger and hence require more than 16 bytes of storage, the result should be truncated $\bmod 2^{128}$.

That is fine, due to the extremely small probability of wrapping, but there are other parts of the document that aren't straightforward.

The value of the multiplier/start point $H = E_k(0)+2$ prevents the pathological cases $H = 0$ and $H = 1$.  ($H = -1$ is also prevented by the construction because $E_k(0)$ is too small.)  But if $E_k(0)+2$ is either $2^{128}$ or $2^{128}+1$, what is supposed to happen to the math?  Is supporting multiplying by a 129-bit number required to handle this case?

I was considering supporting both GCM and SGCM in a client-server application, with SGCM being used when the client is run on a machine without x86 pclmulqdq / ARM pmull.  I don't think there are security considerations about supporting both based on the client's choice.


texts: Should a tweak value be secret like a key or visible like an IV?

texts:
In tweakable block ciphers the tweak acts some ways like part of the key and in other ways, acts like an initialization vector.

Should the the tweak remain secret like the key or visible like the an initialization vector. Or perhaps this may differ from one algorithm to another?


texts: Triple-DES DUKPT CBC PIN variant vs Data variant

texts:
Does any know the difference between triple des dukpt decryption algorithm with PIN variant and Data variant?

I have done Triple DES DUKPT PIN variant, which generate session key from KSN and BDK. And then decrypt message using the session key.

How about Data variant? How is it different from PIn variant?


texts:
I was going through these presentation slides (PDF) on  Crypto 2013.

It summarizes the paper, Factoring RSA keys from certiﬁed smart cards: Coppersmith in the wild.

In the last slide, it was mentioned that one possible future work to be done is to use the “Adi Shamir's secret database of all primes” to attempt breaking RSA-1024. I tried to Google for “Adi Shamir's secret database of all primes”, but I can't find anything. Does anyone have any idea about this "database"?


texts: How well does scrypt perform on different architectures / OSes?

texts:
The scrypt algorithm seems to be a prominent feature in the "CPU friendly" Bitcoin clones for the proof-of-labor part. I've heard claims that it's relatively slow on Windows and/or Intel compared to Linux/AMD.

Is this true? By how much? Does anyone have concrete data on this? Is there a difference between 32 bit and 64 bit OS?

Bonus : could it be implemented more efficiently (power consumption and/or hardware cost wise) on dedicated hardware?


texts: What libraries do people use to implement and evaluate cryptography protocols?

texts:
I want to implement this credential system: “Anonymous Credentials Light” (PDF). The implementation would involve some zero-knowledge proof and some exponentiation.

For some basic group computations like $g^x$, do people usually just come up with their own implementation or is there some famous library that provides such basic operations? If, what would be some of the possible libraries or implementations I could (or should) start with?


texts: Elliptic Curve Crypto, is a distributed signing method possible using Shamir's Secret Sharing?

texts:
Note: A distributed signature scheme exists for RSA:
Practical Threshold Signatures, Victor Shoup.
Is it possible to adapt such scheme for ECC?

A centralized signing machine is vulnerable to attackers

In the situation where a private key has been distributed over R number of machines, which each hold a part of the secret, these R machines can send their share to the signing machine, which will recombine the private key, using the R parts received, in order to sign messages.

This is not satisfactory, because the attacker now only has to attack the signing machine, and wait until it has recombined the private key in order to steal it.

Partial signatures

If sig=sign(sk,m) is the elliptic curve cryptography function to sign a message m with private key sk, yielding signature sig, and if shamir(sk) = [shsk1, shsk2, shsk3, ..., shskR] the function that produces a vector of Shamir secret parts, then the partial signatures would be:

shsig1=sign(shsk1,m)
shsig2=sign(shsk2,m)
...
shsigR=sign(shskR,m)

Since it is not practically possible to retrieve the private key from a ECC signature, it is also not practically possible to retrieve the shamir secret from a partial ECC signature. Therefore, it would be safe to send on such partial signature to the signing machine.

How to recombine the partial signatures?

Now we need a function combineShamirPartialSigs, where:

sig=combineShamirPartialSigs(shsig1, shsig2, ... , shsigR)=sign(sk,m)

In other words, the combination of partial signatures should be equivalent to the signature of the combined private key sk.

Progressive signing

Preferably, such function would even be able to sign progressively:

shsigP1=sign(shsk1,m)
shsigP2=combinePartialSigsProgressively(shsig1,shsk2,m)
shsigP3=combinePartialSigsProgressively(shsigP2,shsk3,m)
shsigPR=combinePartialSigsProgressively(shsigP[R-1],shskR,m)

=sig

The last machine R to sign progressively would then automatically produce the final signature sig.

Security value of this function

This kind of functions would solve a serious security problem. The R machines would not send their secret parts to the signing machine, but produce partial signatures by themselves and send those instead, or even gradually combine the signature by themselves. It would be pointless for the attacker to attack any centralized signing machine, because at no point in time it would know the private key. This function would protect a distributed signing infrastructure from attackers, by keeping its core secrets distributed at all times.

Question

Does such function exist? Would it be possible to construct such function?


texts:
I'm getting this strange result that SHA-512 is around 50% faster than SHA-256. I'm using .net's SHA512Managed and SHA256Managed classes. The code is similar to the one posted here but I'm referring to tests taking caching into account (from the second time reading the file onwards it seems that it's cached completely). I've tested it several times with the same results.
My question is: is this logical or must there be something wrong with my test?


texts: What is different between a hash function and permutations with repeats

texts:
Are secure hash function outputs different from permutation sets of the same length and value? If yes please explain how they appear differently.

For example, MD5 would produce

8743b52063cd84097a65d1633f5c74f5

A non standard permutation algorithm that is impossible to inverse without a key would appear to be the same and be just as secure.


texts: Let (P, V) be any ZK protocol, then the protocol is WI. --> help with proof

texts:
In the amazing paper "Witness Indistinguishable and Witness Hiding Protocols
" by Shamir and Feige.

Theorem 3.3: Let (P, V) be any ZK protocol, then the protocol is WI.

The sketch of the proof involves a distinguisher $D$, which I never saw used in the context of ZK, and I don't know it's definition.
Can you define $D$ ?
Can you point me to the proof of this theorem or just walk me through it loosely?


texts: How do different block sizes affect the throughput of GPU implementations of AES?

texts:
I am confused about the effect of different block sizes on AES performance. As you can see here, there is a huge gap between the throughput of different block sizes. As far as I know, every 16 bytes must be encrypted separately, but I don't know what would happen if the block sizes would be increased.

How would 16 bytes of a 1024 byte block be encrypted? Indeed, I can't understand the effect of block size to throughput!


texts: I am studying RSA Dynamic Accumulators and I have a question: why is it simpler to calculate the new accumulator value after a deletion if the secret $\phi(N)$ is known? Is possible to calculate the deletion only with the RSA modulus $N$?


texts: Security of a custom AES-based attack model

texts:
Provided that:

$AES(plaintext, key)$ is the standard AES block cipher for a 128 bits block.
$\oplus$ is the standard XOR operation.
$K$ is a constant 128 bits pseudorandom value, which is used as the key for AES operations, unknown to the attacker.
$A$ is another constant 128 bits pseudorandom value, unknown to the attacker.
$B$ is a variable 128bits pseudorandom value, unknown to the attacker.
$C$ is a 128bits value which is known and can be chosen freely by the attacker.

An attacker can:

Obtain the value of $AES(A, K)$ (which is constant).
Obtain the value of $AES(B, K)$, for as many different $B$'s as he wants (note that the attacker cannot choose the value of $B$).
Test if $C = AES(A \oplus B, K)$; he can also obtain the value of $AES(B, K)$ being these 2 $B$'s the same value.

Can the attacker take advantage of this knowledge? For instance, could he guess a value for $C$ that is equal to $AES(A \oplus B, K)$, or recover $K$, $A$ or $B$?


texts: Generating sets of unreadable/secure and unique random numbers

texts:
In the process of doing some research, I stumbled across the following two claims on the PokerStars website.

  We do record all of the hole cards in all real money hands. This is an
  important tool to help us investigate fraud and collusion. However,
  this information is not accessible to anyone until after the
  conclusion of the hand; it is not transmitted to our database until
  all action is completed and the pot has been awarded.

  To be clear: Nobody in the public or employed by us can obtain
  information from the servers to find out the hole cards of any hand in
  progress. Nobody in senior management, none of the software
  developers, no operational representatives. Nobody at all.

This got me thinking, how would you go about writing such an algorithm?

Let's start with the following requirement:

"Generate a collection of 52 random numbers representing a deck of cards in such a way that no malicious third party could determine which cards were generated--even if they had direct access to the memory of the computer generating the sequence. This sequence of encrypted numbers must be reversible, but not until the completion of the game."

My first attempt at designing a solution to this problem went along these lines:

A new hand begins.
Each client in the system generates a new public/private key pair.
Each client in the system makes a request for a tuple of new hole cards. With this request the client sends its public key.
The server receives the request for new hole cards and uses the public key provided by the client to encrypt the random numbers generated and return them to the client.
At the end of the hand the client sends the private key back to the server and the server can now decrypt the hand information.

Unfortunately, such a implementation doesn't address all the requirements (it would work, more or less, if you didn't need to generate unique numbers) and has several flaws, chief among them:

If the client disconnects prior to the completion of the hand the server can no longer decrypt the value that was sent to the client, given that it doesn't have the private key.
The requirement that a deck of cards must not contain duplicate values ensures that somewhere in memory, at some point in time you must store a collection representing the cards which have already been dealt. This completely negates the original purpose of this algorithm as this information can now be potentially read by a malicious third party who has access to the device.

If you're going to be able to log the information you need to log in the event of someone disconnecting before the end of a hand, it seems like you're going to have to be able to reconstruct that information server side. (Is this so?) And if sufficient information is stored server side to reconstruct the data you're trying to keep hidden before the end of a hand, then anyone with access to the server should be able to do it before the end of a hand as well-- it seems like the ability to compensate for a disconnect, and the ability to read hidden information before a hand ends, go...hand-in-hand...

Can anyone suggest a potential implementation of such an algorithm or definitively prove that such an algorithm is not possible?


texts: Probability of SHA256 Collisions for Certain Amount of Hashed Values

texts:
I wonder if you can help me figure out that question:

Is there a known probability function f: N -> [0,1], that computes the probability of a sha256 collision for a certain amount of values to be hashed? The values might fulfill some simplicity characteristics to reduce the complexity of the problem e.g. all of them are of equal difference to each other with a constant difference t or whatever is needed to somehow reduce it to manageable complexity.

In other words: How likely is it to have sha256 hash collisions in a "simple" set of n values?

Yeah, I'ld like to hear your thoughts about that :) Thanks for all helpful comments / answers in advance!

EDIT
Background is: I wonder if it is possible to decide when the change to a 'higher' hash function (like changing from sha256 to sha512) makes sense - not only by having an eye on experiments but by theory.


texts: What's the point of a Meet In The Middle attack using i.e. double AES with throw-away keys?

texts:
What's the point of a Meet In The Middle attack while using, for example, a double AES encryption and using one time keys?
You can recover the keys for a secret message already known and you can't use those keys to retrieve other secret messages.
So why would an attacker use it?


texts: Use ElGamal to solve Diffie-Hellman problem

texts:
Say we are able to decrypt a Elgamal ciphertext $c$ using only the public key. Apparantly it is now possible to solve the Diffie-Hellman problem (given $g^a, g^b$ calculate $g^{ab}$). How?

I know how it works the otherway. When I'm able to solve DH, I found a way to decrypt Elgamal ciphertext. But I can't come up with a good idea for this problem.

I figured since $c=(c_1,c_2)=(v,w)$ maybe $c_1=g^a, c_2=g^b$ such that the plaintext $p=g^{ab}$, but that doesn't work out.

I'm thankful for any tips.


texts:
I recently found this site, proposing a hashing algorithm for passwords.

They describe the following:

pad the password on both sides with SHA1(email) to 4 * length(password)
HMAC(padded password, global salt)
choose a random salt of 22 characters
bcrypt(hmac, salt)

Is this algorithm secure? I think it might be a security flaw to pad the password on both sides with the same text, and I see no point in using a global salt and a salt which is chosen randomly for every password.


texts: Why is a LCG not suitable for use in a cryptographic primitive?

texts:
Two's complement addition (and multiplication) are non-linear with respect to XOR and AND. This means that for bit vectors over $\mathbb{Z}_2$, the operation $a + x$ cannot be expressed as the matrix multiplication $Ax$, where $A$ is some constant matrix derived from $a$.

Because of this non-linear property, why is a LCG often regarded as having bad cryptographic properties? Would it not make a good non-linear step in a cipher?


texts: Is this pairing-based signature scheme secure?

texts:
There are a number of signature schemes on small domains based on bilinear pairings which do not use random oracles. Examples are the Boneh-Boyen schemes and an interesting one from Okamoto which allows for blind, and partially blind signatures.
However all of them use some variant of the Strong Diffie Hellman assumption which (roughly) asks to compute $e(g,g)^{1/x}$ from $(g, g^x, g^{x^2}, \ldots, g^{x^q})$.
The signature scheme I have in mind is this:
Public information: $g_1 \in \mathbb{G}_1, g_2 \in \mathbb{G}_2$, bilinear pairing $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$
Signer secret: $x_1, x_2 \in \mathbb{Z}_p^*$
Signer public: $A=e(g_1, g_2)^{x_1}$, $B=e(g_1, g_2)^{x_2}$
The signature algorithm takes an element of $m \in \mathbb{Z}_p^*$
and computes $\sigma(m) = g_1^{x_1m+x_2}$.
The verification algorithm checks that $e(\sigma(m), g_2) = A^m B$
Forgery seems to require computing $g^{m'x_1+x_2}$ from $(g^{m_1x_1+x_2}, g^{m_2x_1+x_2}, \ldots, g^{m_nx_1+x_2})$ where $m' \neq m_i$.
Is this scheme secure and if so is it used anywhere?


texts: Feige–Fiat–Shamir identification scheme: Question about a part of the ZK protocol

texts:
My question (at the bottom) is in regards to the part of the protocol where the Verifier challenges the Prover by sending a bit b where b = 0 or b = 1.

Example for context

One Time Setup

p = 3
q = 5
n = 15
privKey = 8 (co-prime to n)
pubKey = privKey^2 mod n ⇒ 64 mod 15 = 4

  At this point, the verifier knows:
  n = 15
  pubKey = 4

Protocol: The following is repeated t times

Prover selects a random number < n
randNum = 11
Prover computes x as follows and sends x to Verifier
x = randNum^2 mod n ⇒ 121 mod 15 = 1
Verifier chooses a bit, b = 0 or b = 1, and sends it to Prover as a challenge
Prover computes (privKey^b • randNum) mod n as a response

  By choosing a bit b = 0 or b = 1 the Verifier chooses to see either:
  Case 1
  b = 0: randNum mod n ⇒ 11 mod 15 = 11 (if randNum is < n, verifier will receive randNum)
  OR Case 2
  b = 1:(randNum • privKey) mod n ⇒ 88 mod 15 = 13

Case 1: b = 0
As a response from Prover, Verifier receives: 11
Verifier computes:

11^2 mod 15 = (x • pubKey^b) mod n
11^2 mod 15 = (1 • 4^0) mod 15
121 mod 15  = 1 mod 15
1 = 1 //passes the test

Case 2: b = 1
As a response from Prover, Verifier receives: 13
Verifier computes:

13^2 mod 15 = (x • pubKey^b) mod n
13^2 mod 15 = (1 • 4^1) mod 15
169 mod 15 = 4 mod 15
4 = 4 //passes the test

My Question

In Case 1, the Verifier is actually checking that:

randNum^2 mod n = (randNum^2 mod n) mod n

which is essentially randNum = randNum

I don't understand why this part of the protocol is necessary. It seems that all the Prover has proved here is that they've picked a randNum. Anyone who doesn't know the privKey will always be able to do this.

I understand that there is only a 50% chance in any given round that this case will be chosen and that a false Prover (one who does not know privKey) will inevitably fail, but it seems that Case 2, where b = 1, is sufficient for the Verifier to be convinced that the Prover knows the privKey whilst gaining zero knowledge about the privKey and that no false Prover could pass this test.

Why is Case 1 a necessary part of the protocol? I must be missing something.

I hope that's clear, Thanks!


texts: What are Alternatives to basic ROT-n Ciphers which Don't Lose 'Context'?

texts:
I've got this neural network running like a champ on my machine.  The data is concatenated works of shakespeare in a plaintext file.  RNN trains on the data, then gives you a 'sample', aka it tries to freestyle its own shakespeare based on what it has learned.

So now I've encrypted the dataset with a standard mid ROT cipher, and gave that to the NN to train on.  Which it did, and it returned a result which was ROT ciphered.  Decrypting that yielded valid results. As it should have, training on data that kept all its 'context', without randomness, unpredictability, or 'fuzz'.  Not sure if those are the exact words, but you get it.

I'm wondering if there are any other ciphers, or really any other algorithms like compression schemes or what have you, that may yield the same results as my previous experiment?  That training on its encrypted data would likely yield a sample that could then be decrypted accordingly?  Or would most other stuff be 'lossy' in some way?


texts: Why is a known-plaintext attack considered a complete break?

texts:
I read somewhere that if a cipher has a known-plaintext attack, then it is considered completely broken.

Say there is a cipher that someone uses where the algorithm is understood and a known-plaintext attack is trivial to perform, however a ciphertext only attack is as impractical as brute force. The XOR-Cipher with the key length equal to message length, for example.

If the user changes the key for every message sent, then what use is a known-plaintext attack?

It's always been my understanding that if one finds the key to a message they already know but to nothing else, then that is just as useless as not being able to perform a known-plaintext attack at all.

So what use is a known-plaintext attack in a world where a key is never used more than once (effectively a one-pad pad)? How is that "a complete break"?


texts: Is it safe to store both the AES-related data and the PBKDF2-related data (except passwords) in one file?

texts:
Assume an "encrypted data package" file format which includes the following data

PBKDF2

algorithm
salt
rounds
keylen

AES

algorithm & mode
IV
ciphertext

where the PBKDF2 salt and AES IV are generated using a CSPRNG upon individual encryption.

This would make the individual password (used as PBKDF2 input parameter) the only seperately stored data (secret to the "encrypted data package" file) which is stored in a secure place.

Is it safe to store both the AES-related data and the PBKDF2-related data (except passwords) in one file, or are there any cryptographic implications when doing so? If there are implications, what would be the advantages (from a security point of view) of storing the PBKDF2 data separately from the AES data?

When describing potential pitfalls, it would be nice when answers would assume and expand on the following two scenarios:

AES-256-CTR, with the PBKDF2 parameters simply prepended to the ciphertext, and
AES-256-GCM, with the PBKDF2 parameters fed into the AES mode as associated data.

Think of this more as a canonical question, hinting at

*“Do seperate storages resemble security by obfuscation?” and
”What's the minimum data we would need to store in a secure location, and what other data can we safely store next to the ciphertext 'out in the open' so that we don’t introduce cryptographical problems?”


texts: Total password count, given length and pool size

texts:
First, if my password is exactly 8 characters long, derived from a pool of 95 characters, then is the total amount of passwords I can create simply $95^8$                                                                                (6,634,204,312,890,625)?

Secondly, if my password can be upto 8 characters long, derived from a pool of 95 characters, then is the total amount of passwords I can create computed the same way, or would it be something like $95^0$ + $95^1$ + $95^2$ + $95^3$ + $95^4$ + $95^5$ + $95^6$ + $95^7$ + $95^8$ (6,704,780,954,517,120)?

Is the correct term for these called permutations, or search space or key space, or...?

Thanks for the assist!


texts: I have been seeing code using "AES/EAX/NoPadding" but I'm also aware that padding schemes are supported for AES-EAX. I would like to know if choosing NoPadding as a padding scheme has security implications for EAX mode of operation. Thanks!


texts:
I am trying to generate the S-Box provided in the Affine Power Affine paper (PDF) but I'm not sure I understand it fully.

The essence of the paper is this:

AES(i) = Affine(Power(i))

APA(i) = Affine(Power(Affine(i)))

Where Affine is the affine transform and Power is the inverse transform used in generating AES s-box.

Now to calculate the first value of the s-box, we take i = 0

APA(0) = Affine(Power(Affine(0)))

APA(0) = Affine(Power(63))     {Affine(0) = 63}

APA(0) = AES(63)

AES(63) = FB     {You can confirm this from wikipedia's page on Rijndael s-box}

So, APA(0) = FB

But the paper has a table which says that APA(0) is 8C.

There must be a mistake I made because I highly doubt that the paper has an error.


texts: Turning data into seemingly random noise

texts:
I am currently working on a python script that does image steganography, altering the least significant bit on each channel of the image. Now imagine encrypting a file with a bunch of null bytes, or if you want a more realistic scenario, text that has a lot of repeating sequences in it (whole words / characters); Analysing the LSB of every channel of every pixel of this image, will reveal certain patterns and the hidden message can be decrypted easily.

The ultimate goal would be to turn the data given in bits into something that looks like random noise, but can be decoded easily with the given key.

What is a (fast) way to achieve this ?

One idea I came up with after googling for a while is the following:
Generate a random bit sequence, the same length as the data you want to hide, that is based on a specific seed/key. It can be generated again as often as you want supplying the same seed. Now xor the generated bit sequence with the data provided and use this hopefully random looking binary data as the basis for the pixel modifications.

Is this (more or less) secure from a cryptographic standpoint provided the evil decoder doesn't know the algorithm ?


texts: Finding the period of a function with a single output qubit - impact on RSA

texts:
In this paper,May and Schlieper claim that one can find the period of a function $f()$ by embedding $h \circ f = h(f(x))$ for input $x$. This would have the immediate consequence of reducing the number of output qubits. What's more, they say that even a one-bit hash function would be enough to run Shor's algorithm and get reasonably good results. This is at the price of performance.
My questions are, how reasonable are these claims? What is the impact on post-quantum RSA security? Post-quantum RSA security is considered by some people as not that worrisome since it requires a non-negligible number of qubits to be practically broken.


texts: Prove that the following private-key encryption scheme is not CPA-secure

texts:
Consider the following private-key encryption scheme : The shared key is k $\in$ {0,1}n. To encrypt the message m $\in$ {0,1}n, choose random r $\in$ {0,1}n and output $(r, F_r(k)\oplus \overline{m})$, where $F$ is a block cipher and $\overline{m}$ is the bit-wise compliment of m. Is this scheme CPA secure?

What is the importance of bit-wise compliment in this question?

Also, it does seem that the scheme is CPA secure because one is performing a $\oplus$ of a message string and a random string (it would change for every message as we pick a random r for each m)