texts: Cryptographically strong pseudo-random seq. generators

texts: If a pseudo-random sequence generator is built so that it uses an n-bit seed and outputs a string that is of length x. Let's say one wants to generate a bit string of length y and uses the previous PRSG over and over to obtain y bits out of the x bits produced per run. In order to stop repetitions the last n bits of each x bit output is used as a seed for the next output. Why is this not cryptographically strong?


texts:
When I type in any plaintext to an Enigma machine (Enigma machine emulator) the substitution does not seem to follow any pattern. In other words, there is no cycle in the use of enciphering alphabets (defined as the number of switches done when turning a plaintext letter to a ciphertext letter - which can vary from 0 to 26).

But since the key is the alignment of the rotors, there must be a finite key length even though it probably is longer than any plaintext ever would be. I imagine if you keep writing long enough, the rotors will eventually align in a way they already were. If I'm right - how long is the key?

And if the key is much longer than any plaintext, wouldn't that mean the Enimga is a one-time pad? From what I can read, the OTP is defined as an algorithm with a key longer than the plaintext. Is this wrong?


texts: What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?

texts:
The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this the "normal representation". However, in lattice based crypto, the elements of the field are represented by $\{-(q-1)/2, \dots, (q-1)/2\}$, let's call this the "lattice representation".
What is the difference between these two representations? Why is the second one used in lattice crypto? Would it work if the normal representation was used instead?
I would also be very grateful if someone could show an example of how $\mathbb Z_7$'s elements $\{0, 1, 2, \dots, 6\}$ are mapped into the other representation.


texts: What is the fixed point attribute of DES (when used with weak-keys)

texts:
I've heard in some lecture that the weak keys in DES implies the existence of $2^{32}$ fixed points in the algorithm, i.e. that $DES_k(x)=x$ for $2^{32}$  such $x$'s.

I couldn't find anything about that issue, can you give some reference or explain it here?


texts: Constructing an XChaCha20-Poly1305 Equivalent using FIPS-140 Primitives

texts:
I am playing around with the idea of modelling clustered data storage as a series of AEAD messages. XChaCha20-Poly1305 has nice properties for my intended design, as the ability to use random IVs decouples constructing AEAD messages from the state of the storage cluster. However FIPS compliant primitives would be a business requirement in a production implementation.
AES-GCM is the obvious first choice, however its 2^32 invocation limit for random IVs does not lend itself well to data storage. The total write throughput might be 100s of TiBs over the lifetime of a system. Having a global monotonic counter, like the FIPS specification suggests, is difficult to implement in my case. The architecture doesn't have a notion of a "secure global clock" (at least not one that wouldn't be vulnerable to Replay or Sybil attacks).
Is it possible to construct an AEAD Cipher with similar properties to XChaCha20-Poly1305 using only FIPS-140 primitives?
The properties I am interested in are:

Single pass encryption.
Hardware/FPGA implementation friendly.
A nonce can be any random value. (No global state to track)
A large upper bound on maximum invocations per key. (~2**50)
The primitives are listed in the FIPS-140-3 standard.

I already have a scheme in mind, detailed below. I'm interested in feedback on how it could be improved, or if there would be a better alternative I've overlooked. I'm aware of AES-GCM-SIV, but who knows when, if ever that will become an approved function. An alternative could be AES-XTS + KMAC, however that would be quite resource intensive.

Scheme
Derive a random <Key, IV> pair for each AES-GCM invocation using a salt, and transmit the salt as part of the associated authenticated data.
State:
Let {M} be a pre-shared master key of at least 256 bits.
Let {S} be a randomly generated salt of at least 256 bits.
Let {I} be associated data relevant for generating the key. May be empty.
Let {P} be the plaintext message to encrypt.
Let {AAD} be associated data to interpret the ciphertext message.
Let {KDF} be a key derivation function listed in NIST SP 800-56C.
Let {ENC} be a FIPS-140 compliant AES-GCM encrypt function.
Let {DEC} be a FIPS-140 compliant AES-GCM decrypt function.
Let {AUTH} be a FIPS-140 compliant AES-GCM authentication check function.
Let {C} be the ciphertext.
Let {T} be the authentication tag.
Let {MSG} be the final AEAD message.

Encrypt Procedure:
Generate a derived Key and IV, let {K, IV} = KDF(M, S, I)
Construct the AEAD header, let {HEADER} = {AAD || S}
Generate the ciphertext and tag, let {C, T} = ENC(HEADER, P, K, IV)
Output the final message, let {MSG} = {HEADER || C || T}

Decrypt Procedure
Extract the salt from the AEAD header, let {S} = MSG.HEADER.S
Generate a derived Key and IV, let {K, IV} = KDF(M, S, I)
Validate the AEAD message, let {res} = AUTH(MSG, K, IV)
if res is FAILED, output error.
else Extract the ciphertext, let {C} = MSG.C
Output the plaintext, let {P} = DEC(C, K, IV)


texts: Chosen plain-text Attack on DES-X with roughly $2^{64}$ DES operations

texts:
Here is the quote from P. Rogaway,The security of DESX

  "the effective key length of DESX with respect
  to key search is at least 55 + 63 - lg(m) bits"

where m is the number of chosen plaintext/ciphertext pairs.

So how can I attack DES-X with roughly $2^{64}$ DES operations assume we have unlimited storage?

I know that a simple exhaustive key search(~ $2^{120}$ DES operations) can be optimized to $2^{118}$DES operations by the key complementation property.

How can this property help if we have more plaintext/ciphertext pairs?

If we have $2^{64}$ $(p,c)$ pairs, how do we use that to recover all 3 keys? I can only think of using 2 $(p,c)$ pairs to get rid of $k_2$ by simply xor them.


texts: Bulletproofs with ranges not in power of two

texts:
I am new to bulletproofs. From what I understand, if I was to do a range proof using bulletproofs, both the start and end number have to be a power of 2.

is there any algorithm/approach which can be used to expand this to numbers that are not powers of 2?

Example: find if a number is in the range 18 to 65?


texts:
I read this post from Ben Tasker describing how to take control of a powerline network. Since I am interested in security, I tried to do the same thing, to see if it was possible. I used Devolo devices, since those are the only ones I have.

I followed the described steps, and failed in "generating the password from MAC". The password generated by openplc using the mac2pw program is incorrect (I checked by comparing the generated password with the one printed on the device).

I have two openplc versions, one from June 2014, and the latest. The latest includes some random parts and prints in an odd format, dunno why, specially because the base algorithm is the same. The oldest prints the password in the expected format.

Following Ben's reasoning, it is most likely that Devolo used a different algorithm for MAC -> password conversion. How could we discover what algorithm is used by Devolo? I have no experience in cracking algorithms, but I would start with:

Changing the order of the operations
Changing any constants to a large range of values

If these don't work, we could assume that Devolo used some other algorithm not based on the one present in openplc. If that is so, how could we discover such algorithm?

Thanks in advance


texts: Can I prove my app uses randomness right way?

texts: We are developing an iOS app which employs Shamir Secret Sharing algorithm. We made all possible steps users can trust us. We can't remember their secrets nor we can save encoded fragments. But they still may not trust us with randomness. Is there any cryptographic method how user can verify we are using random number generator honestly and have no malicious interests?


texts:
Let $A$ be a set of size $n$. Given a random seed $s$, I am looking to build a pseudo-random random permutation $\pi_s: A \rightarrow A$ such that $\pi_s(a)$ is fast to compute for every $a \in A$. By "fast to compute" I mean significantly faster than $O(n)$ time, e.g. $O(1)$ or $O(\log n)$ time.

One suggestion is to use Feistel networks or MiMC. Any other suggestions?


texts: What value for a Rfc2898 (PKBDF2) is overkill?

texts:
I am working on a project which needs to share messages, and part of that project is deriving a password, I am currently using a value of 65537, totally arbitrary (it is $2^{16} + 1$, so not TOTALLY) and that takes about 1-second to compute. but, I just wondered what value or iteration count is enough?

Note its just a hobby project, not a federal info. transfer thing.


texts: I am working on securing a chat application, and I am not sure about which block cipher mode I should use. I am aware that I should avoid ECB as it's insecure, but what about CBC? I have watched several videos about block cipher modes, and I have read about it too, but I can't figure out what to use and why.


texts: I have two network endpoints that need to use the same derived key.  Can the server send the salt to the client 'in the clear'?


texts:
So I've been reading about salt, and am confused about why the length is so critical. From my understanding salt is used for protection against pre-computed attacks.

Say I have a single password that is hash with salt length n. Suppose this hash and salt is accessible to the attacker. My questions are as follow:

If the n is too short, is the problem that a pre-computed rainbow table may already exist?
If n is long enough that a pre-computed rainbow table doesn't exist, what function does a longer salt serve? A brute force attack would simply add the n length salt to each hash it's generating. 50 bit n, 500 bit n. No difference, because the salt is known and simply added to all the brute force password values being hashed.

So to summarize, when trying to crack a single salted password hash, as long as n is long enough that a rainbow table doesn't exist, then the salt length n adds no security to the hashed password. Is this true?


texts: Any ideas on login using Digital Signature PKCS

texts:
I am curious to know about possibility to login into web application just by identifying the user based on digital signature in usb token.

any reference in this direction?


texts: Find collision in Ajtai's hash function using short vector

texts:
Background

What is Ajtai's hash function?

Given a matrix $A \hookleftarrow U(\mathbb{Z}_q^{n \times m})$ and a column vector $\vec{m} \in \mathbb{Z}_d^m$, the hash of the message $\vec{m}$ is given by

$H(\vec{m}) = A\vec{m} \mod q$

Ajtai's SIS-lattice

The corresponding lattice for $A$ denoted by $L^{\bot}(A)$ is defined as all vectors $\vec{v}$ such that $A\vec{v}=\vec{0}$, in other words $L^{\bot}(A)$ is the kernel of $A$. Thus as far as I understand, to find a basis for $L^{\bot}(A)$ is essentially equal to finding a basis for the kernel of $A$.

The SIS-problem

The $\beta$-SIS problem is the problem of finding a non-zero vector $\vec{v}$ such that $A\vec{v}=\vec{0}$ and $\|\vec{v}\|\le \beta$. This problem is known to be hard.

Is the hash function collision resistant?

Finding a collision for the hash function is as hard as solving the $2d\sqrt{m}$ SIS-problem. That means, given a collision $(\vec{x}, \vec{y})$ we can easily compute a short vector in $L^{\bot}(A)$ as $\vec{x}-\vec{y}$.

Why does it work? We have a collision, i.e $A\vec{x}=A\vec{y} \rightarrow A(\vec{x}-\vec{y})=\vec{0}$, so the vector $\vec{v}=\vec{x}-\vec{y}$ is in the lattice. Next, due to triangle inequality we have that $\|\vec{v}\| \le \|\vec{x}\|+\|\vec{y}\|$. Since both $\|x\|_{\infty} \le d$ and $\|y\|_{\infty} \le d$, it follows that $\|\vec{v}\| \le 2d\sqrt{m}$.

Question

Now, my question is; is it possible to go the other way around? That is, is it possible to find a collision for Ajtai's hash function given a short non-zero vector found e.g using Lentra-Lenstra-Lovász lattice reduction algorithm?


texts:
What is the complexity of ECB in terms of Time and Memory?

and also in OFB? I can't find it in the internet, so I decided to ask it in here.


texts: Does it make sense that a hash is separated by hyphens

texts:
I'm trying to solve a challenge that is no longer active. I failed it when it was active, and I still can't resolve it. The challenge showed me a hash, and I have no idea what kind it is, and how does it make sense that parts of it are separated by hyphens?
I thought about md5 , is it possible?
14d6532f-aefb-49c7-b418-89ddff7002d9


texts: How to Prevent Correlation Power Analysis Attack on AES?

texts:
Which techniques could be applied to AES to prevent these kind of attacks?

I can just think of creating noise with a parallel process for random computation, so the signals have the combination of that process and the crypto process.


texts: What is a "constant time" work around when dealing with the point at infinity for prime curves?

texts:
I've been working for some time, on designing a constant time solution for dealing with the "point at infinity" for prime curves. So, far I'm using the Standard Projective Coordinates for doing fast, Point Addition and Doubling operations, and my implementation uses a "window" approach to do scalar multiplication.
But, I do not know, how to implement addition with the point at infinity in such a way, that it takes the same amount of time, as any other point.
void PointAdd(POINT * R, POINT *P, POINT *Q ) // has many more args
   like curve etc.
{
     if(zero(P->z)) {
         copy(R, Q);
         return;
     }
     if(zero(Q->z)){
         copy(R, P);
         return;
     }
     /*Do other calculations*/
}

Since the z coordinate is an important entity in the Elliptic curve point addition formulas for projective coordinates, it being zero, makes the equations result in a wrong answer, if we plug such a point for PointAdd function unless both $P=Q=O$. I believe, that this if ... else  like checking will crush my implementation's purpose, of being side-channel resistant.
Is there a constant time solution to circumvent this, in a side-channel resistant way, or are there coordinate systems/addition-doubling formulas, that intrinsically, support the operations with the point at infinity $(0:k:0)$, where $k$ is an element of $F_{p}$?


texts:
Given a symmetric encryption scheme with $|K| = |C| = |M|$ that provides perfect
secrecy, it is possible to share a secret $s ∈ M$ between two players by giving one
player a key $k ∈ K$ and the other player the ciphertext $c =$ Enc$(k$, $m)$. Show that
this construction results in a perfect $(2; 2)$-threshold scheme.

I don't know how to do this. Would I go down the route of Shamir's threshold scheme?I know since $|K| = |C| = |M|$ provides perfect secrecy then for every choice of $m$ and $c$, there exists a unique key $k$ but can't see if that helps in any way..


texts:
Does the size of the cryptogram affect the possibility of breaking it?
In the context of symmetric and block algorithms.
Does the format and earlier processing of the document (compression, changing the document format) affect the possibility of its cryptanalysis?


texts: AES, CMAC and "3 pass authentication protocol" Explained

texts:
I am struggling a bit to understand how authentication systems are properly used in NFC tag environments so I'm posting this thread to clarify some concepts.(In advance, this is not my field, so suppose gaps of knowledge)

AES : Its a ciphering algorithm based on symmetric keys (both sides have same key, being it able to cipher and decipher texts), the message is chunked in 10 parts, then each one will be encrypted (using the master key, and several transformation are made on a matrix), to be all joined together afterwards.

This standard is only for encryption and doesn't apply any authorization feature.
I suppose that only the master key is used to accomplish the ciphering.

(I read some thread talking about "key generations" from the master key, so maybe they are used in the algorithm instead? Is it not related at all? )

Its used to avoid "Passive attacks".

CMAC : Gaps here, I don`t know which of them it is. (or maybe none it is)

-It is an authentication protocol(MAC) where the input is a ciphered text (AES previously used), being able to satisfy the authentication part. (Data integrity covered by AES algorithm).

-It is an authentication protocol(MAC) but the input is a chopped plain text( no AES previously used), then the protocol is used along with some AES blocks to satisfy the authentication and integrity parts.

An explanation of what CMAC is will be truly welcome. ( I starting to think that is related somehow with Encrypt-then-MAC procedure)

It is handy to avoid some "Active attacks".

3-Pass-Mutual-Authentication : I think it is just a procedure when the CMAC it is used on both sides but many times, validating both devices if all of them give an positive response. ( I know that there more steps but I'm trying to figure out the general view of this)

Any sort of information to clarify all of this will be grateful, I know that all of them are related but I cant see the overall view.


texts: In Lattice Cryptography, why is it hard to find short vectors if given long vectors?

texts: In lattice cryptography it seems like giving out long vectors for a lattice that can be drawn from much shorter vectors (generating an identical lattice) is somehow useful for public-private key schemes and similar. Why exactly is it hard to find short vectors if given long vectors, can't the lattice just be generated and then the shorter vectors discovered super easily?


texts: c# Correct Triple Des Block Encryption Usage

texts:
I found the below code online, but in its original state, the encryption was not using any padding (Padding.None), and was encrypting in blocks of 8. I wasn't able to get this code to properly encrypt / decrypt data so I was forced to have it encrypt the full length of the text. Is there something fundamentally wrong with what I have done? If so, could someone please show me the proper way to encrypt text in blocks of 8?

// 168-bit (three-key) 3DES (Triple-DES) encrypt a single 8-byte block (ECB mode)
// plain-text should be 8-bytes, key should be 24 bytes.
public byte[] TripleDesEncryptOneBlock(byte[] plainText, byte[] key)
{
    // Create a new 3DES key.
    TripleDESCryptoServiceProvider des = new TripleDESCryptoServiceProvider();
    // Set the KeySize = 192 for 168-bit DES encryption.
    // The msb of each byte is a parity bit, so the key length is actually 168 bits.
    des.KeySize = 192;
    des.Key = key;
    des.Mode = CipherMode.ECB;
    des.Padding = PaddingMode.None;
    ICryptoTransform ic = des.CreateEncryptor();
    byte[] enc = ic.TransformFinalBlock(plainText, 0, 8);
    return enc;
}
public byte[] TripleDesDecryptBlock(byte[] plainText, byte[] key)
{
    // Create a new 3DES key.
    TripleDESCryptoServiceProvider des = new TripleDESCryptoServiceProvider();
    // Set the KeySize = 192 for 168-bit DES encryption.
    // The msb of each byte is a parity bit, so the key length is actually 168 bits.
    des.KeySize = 192;
    des.Key = key;
    des.Mode = CipherMode.ECB;
    des.Padding = PaddingMode.None;
    ICryptoTransform ic = des.CreateDecryptor();
    byte[] dec = ic.TransformFinalBlock(plainText, 0, 8);
    return dec;
}
// Encrypt Text
textBox5.Text = ByteToString(TripleDesEncryptOneBlock(StringToByte(textBox5.Text),
    StringToByte("1 2 3 4 5 6 7 8 9 1 1 2 ")));
// Decrypt Text
textBox5.Text = ByteToString(TripleDesDecryptBlock(StringToByte(textBox5.Text),
    StringToByte("1 2 3 4 5 6 7 8 9 1 1 2 ")));

My Related question on stack overflow


texts:
As you know SAM Modules are used mainly in the electronic payment industry. Due to the low security of key storing in general storage devices or MCUs, Manufacturers used SAM modules for secure storing and transfering data between processor and the end point card reader. In some (e.g. SAM AV2 series from NXP) both connection between MCU-SAM and MCU-Reader can be secured. But the thing I can't understand is that the MCU and the SAM still must present their keys to each other for authenticating and because of this still must the key be stored in the MCU and how do they introduce themselves to each other securely? How do the SAM module and the reader secure connections?
EDIT: Let me explain more:My question is about procedure of identifying between MCU-SAM & SAM_Reader,Are we need to store a key(derived key or Master one) in the MCU?if yes is it safe to storing it in general MCU's memory?if not how MCU & SAM authenticate each other without key ?is SAM's internal MCU programmable?whats procedure of authenticating between SAM-Reader & Reader-Card?


texts: What are some potential applications of trilinear mappings?

texts:
In "Applications of Multilinear Forms to Cryptography" Boneh and Silverberg give "one-round n-way Diffie-Hellman key exchange protocol" as a potential application of n-multilinear mappings.

If we focus on trilinear mappings in particular, what are some other applications?


texts: Secret-suffix MD5 as secure PRF (not MAC)

texts:
In standard secret-suffix fashion, assume we compute the PRF of some message $m$ as $MD5(x || k)$. Preneel and Van Oorschot showed in [1] that this secret-suffix method is unsatisfactory for constructing a secure MAC. (Particularly because MD5 is not collision resistant and therefore the scheme is susceptible to forgeries.) But does that also mean this is not a secure PRF?

[1] http://people.scs.carleton.ca/~paulv/papers/Crypto95.pdf


texts: In layman's terms, how does Shor's algorithm work?

texts:
I've just been reading up on Shor's algorithm, and I find it both fascinating and baffling. I don't understand much about it, other than that it can factor semiprimes in polynomial time.
Could someone explain how it works in layman's terms and why it is reliant on quantum computing?
Keep in mind that while I understand quantum computing basics (i.e., it uses photons instead of electrons, and bits are replaced with qubits that can be 0, 1, or a superposition of both), I don't know anything in-depth about it. I know it's supposedly super-fast compared to classical computing mechanisms.


texts: Compute ln function of a Paillier encrypted value

texts: If I have an encrypted value $Enc(x)$ with Paillier cryptosystem, is it feasible to compute an encryption form of $\ln(x)$ or its approximation using homomorphic properties? The input $x$ is always positive. The $\ln$ function satisfies $\ln(1)=0$ and the derivative of $\ln$ function is $1/x$. Or if I want to compute its approximation, what other information do I need?


texts: Known-plaintext attack on two-dimensional affine cipher

texts:
Problem:

We have a two-dimensional affine cipher with $n = 2,\,\,\,\mathcal{P} = \mathcal{C} = {\mathbb{F}_{16}^2}$, where $\mathcal{K} = \{ A,\,\,b\} $ and $b = (0,0)$. The encryption and decryption is in ${\mathbb{F}_{16}} = {\mathbb{F}_2}[x]/\left\langle {{x^4} + x + 1} \right\rangle $. The task is to recover first part of the key - $A$ given two plaintext-ciphertext pairs: ${e_K}((d,5)) = (7,4)$ and ${e_K}((3,1)) = (d,c)$. A known-plaintext attack should be applied to find $A$.

Some observations:

For a typical one-dimensional case in ${\mathbb{Z}_{26}}$ this task is easy. All we need to do is to solve for $A$ ${e_K}(x) - {e_K}(y) \equiv A(x - y)\,(\bmod \,26)$, considering $\exists \,{(x - y)^{ - 1}} \in {\mathbb{Z}_{26}} \wedge (x - y){(x - y)^{ - 1}} \equiv 1\,(\bmod \,26)$ is true. In this case we just multiply both sides by ${(x - y)^{ - 1}}$ and get the value for $A$.

Now in my case its more complicated. The difficulties come from the fact that we need to perform all calculations in ${\mathbb{F}_{16}} = {\mathbb{F}_2}[x]/\left\langle {{x^4} + x + 1} \right\rangle $ and the plain text - cipher text data is in hexadecimal format. Furthermore we are dealing with $2 \times 2$ matrix not just simple decimal value...

Solution attempt:

Based on the one dimensional case i tried to solve for $A$ using $${e_K}(x) - {e_K}(y) \equiv A(x - y)\,(\bmod{x^4} + x + 1)$$

$\begin{gathered}
  x = \left[ \begin{gathered}
  d \\
  5 \\
\end{gathered}  \right] = \left[ {\begin{array}{*{20}{c}}
  {{x^3} + {x^2} + 1} \\
  {{x^2} + 1}
\end{array}} \right],\,\,\,\,y = \left[ \begin{gathered}
  3 \\
  1 \\
\end{gathered}  \right] = \left[ {\begin{array}{*{20}{c}}
  {x + 1} \\
  1
\end{array}} \right] \\
  {e_K}(x) - {e_K}(y) = \left[ {\begin{array}{*{20}{c}}
  {{x^2} + x + 1} \\
  {{x^2}}
\end{array}} \right] - \left[ {\begin{array}{*{20}{c}}
  {{x^3} + {x^2} + 1} \\
  {{x^3} + {x^2}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
  {{x^3} + x} \\
  {{x^3}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
  a \\
  8
\end{array}} \right] \\
  x - y = \left[ {\begin{array}{*{20}{c}}
  {{x^3} + {x^2} + 1} \\
  {{x^2} + 1}
\end{array}} \right] - \left[ {\begin{array}{*{20}{c}}
  {x + 1} \\
  1
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
  {{x^3} + {x^2} + x} \\
  {{x^2}}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
  e \\
  4
\end{array}} \right] \\
  {e_K}(x) - {e_K}(y) = \left[ {\begin{array}{*{20}{c}}
  {{x^3} + x} \\
  {{x^3}}
\end{array}} \right] \equiv A \cdot \left[ {\begin{array}{*{20}{c}}
  {{x^3} + {x^2} + x} \\
  {{x^2}}
\end{array}} \right]\,\,\,(\bmod \,{x^4} + x + 1) \\
\end{gathered} $

How can i proceed from the last step?


texts: Understanding simplification steps when solving complicated equations in Galois Field

texts:
I just encountered a problem when I tried to understand a basepoint conversion from x25519 to ed25519. I can't really wrap my head around how the value of $x$ can be the stated value below? Can someone please, go through the derivation steps of $x$, especially the modular arithmetic part?

From Base point in Ed25519?

  $$ x^2=\frac{1-(4/5)^2}{-1+(121665/121666)\cdot(4/5)^2} \text. $$ Now
  by considering the symmetric representants (that is, from the set
  $\{-(q-1)/2,\dots,(q-1)/2\}$) for the elements of $\mathbb F_q$, we
  can interpret one of the roots of this equation as being positive and
  the other as negative, corresponding to the signedness of their
  symmetric representant. The unique "positive" solution to the
  equation above is precisely
  $15112221349535400772501151409588531511454012693041857206046113283949847762202$.


texts: Major Block Ciphers between DES and AES competitions

texts: DES was announced as a standard in 1976. AES competition started in 1997 and Rijndael was selected as standard in 2000. What are major block ciphers and block cipher designs made/proposed from 1976 to 1997?


texts: Could one construct a cipher that is secure for friendly parties to use but insecure for hostile parties?

texts:
Consider the situation of a nation state (Blue) at war with another nation state (Red). Blue wants to deploy a secure cipher that blue currently can not break, but they are considered that Red could reverse engineer the cipher and use it to secure Red's communication (Red is unable to develop it's own secure cipher).

Questions:

How have governments in the past approached this problem?
How could one design such a cipher?

I have been working on an incomplete (maybe impossible) formulation of such a system. I know that asking is "my cipher secure" questions is frowned upon, but I hope my outline below is free of enough implementation details that it will not be seen in such a light. It is more of a "is my cipher possible" question.

Here is my formulation of a backdoor cipher.

Assume a function $g$, takes as input a integer $s_i$ and outputs a cipher $c_s$. That is, $g$ generates ciphers based on a seed $s$.

$$\text{Let }  g(s) =  c_s$$

The cipher $c_s$ has the property that if one knows $s$ one can decrypt all messages encrypted with $c_s$. Thus, the cipher is safe for Blue to use since Red doesn't know $s$ and can't learn $s$ from $c_s$, but if Red attempts to use $c_s$ Blue can decrypt all their communications.

One could build $c_s$ by appending an encrypted (using a public key derived from $s$) form of the key used by $c_s$ to the ciphertext. That is,

$$\text{Let } c_s.\text{encrypt}(key, plaintext) = ciphertext|publicKey_s(key)$$

While in principal this would work it would not satisfy our scenario above because the backdoor is so blatant and easy to remove. Red could just alter the cipher to not append the encrypted form, $publicKey_s(key)$, of the key.

Instead a more subtle approach would be to create a function $g'$, which still takes $s$ but produces both a cipher $c'_s$ and a function $v_s$.

$$\text{Let }  g'(s) = (c'_s, v_s)$$

The cipher $c'_s$ has the property that some of its keys are insecure and some of its keys are secure. The function $v_s$ produces only secure keys.

Blue can generate and distribute many secure keys using $v_s$.

Best case, Red doesn't realize that some keys are weak and some are strong and thus assumes that Blue would never use a cipher that Blue could break. Red trusting in this uses $c_s$ for secret communications.

Even if the vulnerability comes to light, Blue communication are still secure and Red still can't generate strong keys. Nor can Red use captured keys that were generated by Blue because Blue remembers generating them.

Question: Is this scheme is remotely possible, if so what math could be used to construct it?

EDIT:

I wrote this up as "Imagining a Secure Backdoor Cipher".


texts: What is the smallest last value of sequence of integers from 1, where there is a collision in md5?

texts:
Question is just out of interest.

If we take md5 hash from all integers from 1 to n, what is the first n, where its md5 collides with some previous md5?

Has anyone ever calculated and proved the smallest integer, where the collision occurs?

If not, is there considerations about md5 pseudo-randomness, which make probability of colliding md5-s higher for consecutive integers than for cryptographically random strings (birthday attack -> 2^64)?

This, for example, might be useful to know, when trying to hide real sequential order numbers.


texts: Fibonacci LFSR, recovering previous bits

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

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

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


texts:
This seemed like an option if the hash is unpredictable.

It could be the hash of the message or the hash of the message + some common secret (apart from the key).

The only circumstance in which the hash would be predictable is when the message is the same. In that case, looking at the same nonce/hash wouldn't provide the attacker with any new information.

So it seems like a hash could work like a random number. Would it be safe to use the message hash as the IV in ChaCha?


texts:
Let's say there is a piece of software that uses AES CTR to encrypt different messages using the same key but with slightly different IVs.

So for example,  a 16 byte IV, the 2nd 8 bytes are always the same, but the 1st 8 bytes are random.

How insecure is this?

I know that you shouldn't use the same IV and key. But do similar IVs have the same vulnerability or a different way to attack them?


texts: Information-theoretic bound on leakage by timing measurement

texts:
I'm looking for an information-theoretic bound on leakage by timing measurement. I'm assuming that an attacker

wants to leak out of a black box a secret key of $k$ bits that is secretly injected into the black box;
has written the black box's code (which can read the key and act accordingly), and can craft this code to the point of choosing the duration of a function performed by the black box among $n$ equally spaced durations $t_j=t_0+j/(n-1)$, $0\le j<n$ ($t_j$ is in units of clock period), with $t_0$ known;
can measure the duration of that function with an uncertainty $u$ according to some distribution $U$, with $|u|<1/2$ unless otherwise stated, at each execution of that function.

and I'm looking for a tight upper bound on the number of timing measurements to leak the whole key (so that I can be sure that some of $k$ remains secret if we are below that bound).

An execution leaks at most $\log_2(n)$ bit worth of information by way of timing measurement, thus at least $\lceil k/\log_2(n)\rceil$ timing measurements are required to fully extract the key by that sole mean. That bound can be reached if the attacker further has $\big\lceil\log_2\big(\lceil k/\log_2(n)\rceil\big)\big\rceil$ bits of permanent storage in the black box that survive function execution, and are initially zero (sketch: we write the key $k$ in base $n$, and the permanent storage is used for a counter telling which digit of $k$ is leaked).

Update: I realize that the above bound of $\lceil k/\log_2(n)\rceil$ measurements also applies if the attacker can choose the input of the black box and have the code act accordingly; this makes Q1 and Q2 below far less relevant.

Q1: What if the attacker's code does not have any permanent storage, only a true random number generator internal to the blackbox? What's even an appropriate way to characterize the number of measurements required to leak the key?

Q2: What if in the situation of Q1, the attacker also obtains in addition of each timing measurement some large random input or output of the black box, also available to the attacker's code?

Q3: What if the attacker's uncertainty distribution $U$ becomes significant? Perhaps, consider that $U$ is the discrete uniform distribution on $[0\dots m-1]$; or $U$ is Gaussian; or something in between, like $U$ is the sum of two or three discrete uniform distribution on $[0\dots m-1]$.

Rationale: My true goal (hopefully reached is we can answer Q3 under the conditions of Q2) is assessing the demonstrable effectiveness of a countermeasure to timing attacks in Smart Cards (assumed running synchronously), consisting of inserting a random pause after a sensitive operation, as in Q3. The hypothesis that the attacker has written the code is of course a worst case scenario, crafted in order to obtain an upper bound of the leakage (a lower bound on the number of measurements necessary).
Q2 is asked because, in a real situation where the attacker did not write the code, it is reasonable to believe that there is no equivalent to permanent storage usable by the attacker, but that input (or output) has a deterministic effect on timing. Q1 is an introduction to Q2, without that data dependency.


texts:
If I have some bytes, and I want to compute a secure hash into a prime field which is 300 bits long I can:

Use a nice hash, like sha3_512, and then

modulo my prime field (introduces some bias).
toss bits most significant bits away until the number is < my prime (some bias toward smaller numbers)
toss bits most significant bits away until 300 bits, and then modulo my prime if needed (less bias?).
toss bits most significant bits away until 300 bits, then start over (hash the hash) if the number is too big (eventually converge).  (no bias, slow)
???? some better method ????

How important is the bias overall?

If I'm using the resulting hash as the hash for a EC signature scheme, it's insignificant...since the hash isn't protecting anything... it's just collisions that are a concern, which we've made worse by a fraction of a bit.
If I'm using the resulting hash as a "nonce" to protect a secret value during, for example, an mpc computation, it could be "leaky".  Over many uses of such a scheme someone might be use the bias to attack the key or the mpc.   The same holds for deterministic nonces used to reduce signature malleability, which is why I think they are a very bad idea.  See https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf, for just how bad this is.
If I'm using the resulting hash as the private part of an pairing based signature scheme (which requires mapping a message into the curve) , it seems to me that the bias just causes a similar collision loss.

Has anyone compared masking methods for bias?   Is there a good reference on best practices?  IS there a good analysis of the types of protocols for which such masking is a concern?


texts: Decrypt digital signature using RSA public key with openssl

texts:
I have a digital signature that was created using the following algorithm: a SHA-256 hash of the body of the message is calculated. It is then signed using an RSA private key and the result is base64-encoded.

Now, I have the RSA public key corresponding to that private key which was used to encrypt the hash. I want to decrypt the digital signature using the RSA public key so that it gives me the SHA-256 hash of the body of message that was sent by the server. I can later compare this with the SHA-256 hash of the body of the message that was received.

I am unable to recover the SHA-256 hash (I'm expecting to get 64 hex characters). Here is what I am doing:

I save the public key in the following format in a file, pub.key:

-----BEGIN PUBLIC KEY-----
the key itself
-----END PUBLIC KEY------

With the following command:

openssl rsa -noout -text -pubin < pub.key

It tells me that the key is of length 2048 bits.

I save the base64-encoded digital signature in a file called sig.txt and then use the -verify option of openssl to retrieve the data.

openssl rsautil -verify -in sig.txt -inkey pub.key -pubin

This gives me the error:

RSA_EAY_PUBLIC_DECRYPT: data greater than mod len: rsa_eay.c

Please note that the signature in the file sig.txt is in base64 encoded form.

How can I use the RSA public key to decrypt this signature to recover the SHA-256 hash?


texts: What do associated data and message numbers mean?

texts: I'm reading an article about authenticated encryption and don't understand some inputs to an encryption function. They are associated data, public and secret message numbers. Can you explain me their meanings?


texts: Asymmetric key derivation – Who derives the new pub key can't know the new private key?

texts:
I'm looking for a peer reviewed protocol or algorithm that can do this, preferentially I need something based on elliptic-curves cryptography.

Alice know the main public key of Bob (B-PUB-1).
Alice want to derive a new public key (B-PUB-2) from Bob's public key (B-PUB-1) in an asymmetric way.
The new key correspond to a private key (B-PRIV-2) that only Bob can generate by deriving it from his original private key (B-PRIV-1). This is done with only one communication from Alice to Bob without reply.
The only important use of (B-PUB-1, B-PRIV-1) is to generate several different instances of key pairs (B-PUB-2, B-PRIV-2), to communicate Alice and Bob can use also other keys.

In this way Bob own a new private key corresponding to the public key created by Alice.
Bob now could produce some signature of a message m with B-PRIV-2 verifiable with B-PUB-2.
A fundamental request is that B-PUB-2 and the signatures produced with B-PRIV-2 couldn't be related to B-PUB-1 by no one but Alice.

The purpose is not to allow Alice to be the only one able to verify the signature of the message.
At the contrary Alice will publish B-PUB-2 so everyone will be able to verify that m has a signature corresponding to B-PUB-2 but no one will be able relate this signature to B-PUB-1 and Bob.

The idea under this is that Bob trust that Alice has no interest in reveal his identity ( the fact that B-PUB-2 was derived from B-PUB-1) but Bob can't trust Alice  completely.
She could try to use the generated keys to create fake signatures. So Bob can't simply ask Alice to generate a keypair, publish the B-PUB-2 and send to him the B-PRIV-2.

A sketch of the way I think algorithm could work:

Alice choose some Random Secret
Alice do something with that secret and Bob's public key (B-PUB-1) to
create another key (B-PUB-2)
Alice send the Random Secret to Bob with an encrypted channel, this can be done with normal public key encryption. To send the key Alice can use B-PUB-1 or a completely different Bob's public key if the use of B-PUB-1 for encryption cause security flaw.
Bob obtain the Random Secret and do something with B-PRIV-1 to obtain
B-PRIV-2
Alice publish B-PUB-2
Bob create a message m and sign it with B-PRIV-2
Bob publish the message in anonymous way
Everyone can control the signature with B-PUB-2


texts: How do you verify that an address is related to a private key

texts:
This is my first post. My interest for cryptography is exclusively motivated by cryptocurrencies.
My question is:
If I generate some keys, how do I actually verify that the address is indeed associated with that private key (without the need to test a transaction on the blockchain)? Can we apply this for all cryptocurrencies or is that specific to each one of them?


texts: How do people know decryption is successful?

texts:
Decryption is simply a process of transforming one byte string into another with an input argument private_key. However, if people have no knowledge about the plaintext, how do they know the decryption is successful?

For example, suppose the plaintext is a byte string abcd, and transformed into ciphertext whatever in the encryption process. Then let's assume the decryption process transforms whatever into abcd with one private key, and wxyz with another private key, how do people know which result is the original plaintext?


texts: Is it Ok to reverse the usage of public key and private key

texts: Well things like this, my coworker suggest exchange the private key between server and client and using public key to decrypt message privately, his reason is, this is just the same as normal usage, yeah for just encrypt and decrypt message they work the same. But I wonder is there any weakness in it, make it easier to crack?


texts: Information leak in ElGamal encryption with message in base group

texts:
Assume a finite commutative base group $\mathbb B$, some $g$ in $\mathbb B$, and $\mathbb{G} = \langle g\rangle$ the subgroup that $g$ generates, with choice of $\mathbb B$ and $g$ such that ElGamal encryption would be secure for a random message in $\mathbb G$ (semantically/under CPA).

ElGamal encryption still allows decryption if we use a random message in $\mathbb B$ rather than in $\mathbb G$. How much information about the message can leak if we do this? If necessary to get a result, restrict to $\mathbb B=\mathbb Z^*_p$, perhaps with $p$ an odd prime, and/or to $\mathbb G$ of prime order.

Notation: order of $\mathbb G$ generated by $g\in \mathbb B$ (noted multiplicatively) is $q$; private key $x$ is uniformly random with $0<x<q$; public key is $h=g^x$. Encryption of $m$ random in the message space ($\mathbb G$ for the  standard definition of ElGamal encryption, $\mathbb B$ in the question) generates one-time $y$ uniformly random with $0<y<q$, and computes $c_1=g^y$, $s=h^y=g^{x\,y}$, $c_2=m\,s$. Ciphertext is $(c_1,c_2)$. Decryption recomputes $m$ as $c_1^{q-x}\,c_2$.

It is known that if $\mathbb B=\mathbb Z^*_p$ with $p$ a large prime and $\mathbb G$ of prime order $(p-1)/2$, there's an information leak of one bit: we can determine from the ciphertext if the plaintext is a quadratic residue or not; but nothing else as far as we know. I'm unsure about the many other cases ($\mathbb G$ of smaller prime order, or not of prime order; other base groups).

My motivation for that problem came while answering this question.


texts: Problems when using PBKDF2 to create an ECDSA private key from a password?

texts:
System based on, e.g.:
PBKDF2, ECDSA and authenticator's random challenges.

Key derived from a password would be ECDSA's private key used to sign random challenges.

Is password brute force the only thing I should worry about or is there another threat involved with using such key as a ECDSA seed?


texts: How is NIST's Key Wrap (using AES GCM) different than normal AES GCM Authenticated encryption?

texts: From what I could gather, it seems like that NIST's key wrap (publication) provides similar security like AES-GCM Authenticated encryption. If this is true, why did we need a separate specification for key wrap in the first place ?


texts: Is ChaCha20 alone sufficient for securing data-at-rest?

texts:
I wonder if ChaCha20 alone is sufficient for securing files stored on a disk or should Poly1305 should be used along with it? AFAIK, Poly1305 is used to secure the authentication channel, but for securing data-at-rest, the key can be read from the OS's keystore, which (typically) is fairly secure - correct?

If so, does that mean ChaCha20 alone is good enough?

Thanks


texts:
I have been reading a bit about encryption algorithms. I have come across these two algorithms.My use case is the ability to work with encrypted data and my data will be string data. I see that homomorphic encryption works with only numeric data.

I have read that homomorphic has scalability issues as it creates a 100x increase in encrypted data.

Does one have to use zk-snark along with homomorphic encryption or one of the two can be used?

Which one to use for which use-cases?


texts: Can the precompiles in Ethereum Byzantium for pairings be used for implementation of BBS group signature verification?

texts:
I'm currently implementing a group signature verification on Ethereum and it seems that the Pairing check can only return a boolean.

According to the BBS algorithm, to validate a signature $s$, you need to check $$
e(T_3,g_2)^{s_x}.e(h,w)^{-s_\alpha-s_\beta}.e(h,g_2)^{-s_{\delta_1}-s_{\delta_2}} = (e(g_1,g_2)/e(T_3,w))^c.R_3
$$
Which can also be framed as:
$$
R_3 = e(T_3,g_2)^{s_x}.e(h,w)^{-s_\alpha-s_\beta}.e(h,g_2)^{-s_{\delta_1}-s_{\delta_2}}.e(g_1,g_2)^{-c}.e(T_3,w)^c\\
R_3 = e(s_x.T_3-({s_{\delta_1}+s_{\delta_2}}).h-c.g1,g_2).e(c.T_3-({s_\alpha+s_\beta}).h,w)
$$
Let's supposed, we provide $R_3$ and $s$. Is there a way to use the precompiled pairing contract for this check?
Also, is it interesting to precompute $e(g_1,g_2)$ and other constant pairing and how do you use it efficiently?

Thanks


texts: What is the difference between discrete logarithm and natural logarithm?

texts:
Why we take (base $e$) and (base 2) in natural and discrete logarithm, respectively?
I do not understand the difference between these two concepts.


texts: Can block ciphers encrypt messages larger than the key length?

texts:
I am trying to learn some basic cryptography and I am reading some conflicting statements about block cipher.

My current understanding is that we start with an XOR to obfuscate our data. We can then generate a one-time pad to encrypt our message. The only limitation is that the message length must be less than the length of our single-use pad (making one-time padding impractical for large files).

So we introduce block ciphers which encrypt blocks of plaintext at a time. We generate a key which is essentially a mapping of input to output. An example of a block cipher is AES.

I read that AES would blow up if we tried to encrypt a jpeg file - or any message that is larger than our key size (thus introducing stream cipher). I've also read that block cipher is best used on any known-length message (i.e. any file). The latter makes more sense since we're breaking down messages of any length down into blocks anyway.

Which is true? Am I misunderstanding something?


texts: Complexity of Boudot's zero-knowledge range proof scheme

texts:
According to Camenisch et al. in Efficient Protocols for Set Membership and Range Proofs (see Section 1.2), the range proofs devised by Boudot in Effcient Proofs that a Committed Number Lies in an Interval are based on representing a number as the sum of four squares.

Based on this, Camenisch et al. claim that the complexity of Boudot's scheme is governed by the cost of finding these squares (see Section 4.4 of the paper by Camenisch et al.)

However, studying Boudot's schemes, I do not see any reference to this issue. Rather, Boudot defines the squares involved in the proof as $\tilde{x}^2_1,\bar{x}^2_1$, where $\tilde{x_1} = \lfloor\sqrt{x-a}\rfloor$ and $\bar{x_1} = \lfloor\sqrt{b-x}\rfloor$, where the value being proved, $x$, belongs in $[a,b]$. So the computation of these squares seems quite straight forward.

What am I missing?


texts:
I have been playing around with cRARk and was astonished by the low speed. On a 2015 high-end GPU (GeForce 980 ti), it took roughly 4h 50min to test all passwords composed of an 8-character prefix and 6 small latin alphabet letters (AAABBBCC $a * in the format cRARk uses). This is just over 300 million passwords, which corresponds to 18500 passwords per second.

The RAR file is 164 bytes long and has the identification string:

52 61 72 21 1a 07 00

Is it hardware limitation (I've had performance problem with the GPU), is it that cRARk is slow or is it the nature of RAR archives that they are this slow to crack?


texts: Does Coron and May's paper for deterministically reducing finding  to factoring  work with $\lambda(n)$?

texts:
Samuel Neves in his reply mentioned a method by Coron and May's 2004 paper for deterministically reduce finding  to factoring .
As you all know, we are using $\lambda(n)$ everywhere now for RSA. So question is, does this work for $d$ generated with $\lambda(n)$? The paper seems referring to $\varphi(n)$ only. If it does work, what is the proof?
Also, anybody knows some reference implementation of Coron and May's method in Python or other language?
If it does not, is there any probabilistic method/algorithm to factor $n$ if $e,d$ are known and $ed = k\lambda(n) + 1$ ?


texts: I am curious If every single digital file has a hash  and/or a checksum. When verifying my downloaded files using hdiutil on mac os, about 90% of my files report some sort of checksum. However, when i download .iso files or ubuntu / windows, img’s or iso’s, i’ve noticed many of my image files do not report a checksum. I always assumed that if it was data, it HAS to have a checksum, or it wouldnt be data in the first place. Could someone please tell me weather or not all digital files have a checksum, and if it is possible to have files with non existent checksums? Thank you for any info!


texts: Why are integers considered "little endian" in ChaCha20 function?

texts:
Why the ChaCha20 - IETF algorithm that generates 512 bit keystream per 32 bit counter (that gets incremented), considers "the input words" that form the internal state as little endian ? What will happen if it was considered "big endian" ?

Moreover, we read the byte strings for key, nonce, etc in such a way that we get little endian integers.
For example, if I have a 32 byte key in hex like : 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13:14:15:16:17:18:19:1a:1b:1c:1d:1e:1f

we get

uint32_t key[8] = {
      0x03020100, 0x07060504 0x0b0a0908, 0x0f0e0d0c
                0x13121110 ,0x17161514, 0x1b1a1918, 0x1f1e1d1c
}

I was writing a C++ implementation of ChaCha20 that requires this array to be copied to the right positions in the internal state.  Specifically speaking I'm more interested in using XChaCha20 - Poly1305 - IETF   (as it supports a 192 bit nonce) and for that I have to use a separate function HChaCha20 to generate a 256 bit subkey to be passed to the normal ChaCha20 . But these quotes from the IETF documents (Sec 2.2.1 ) confused me :

  After setting up the HChaCha state, it looks like this:

                61707865 3320646e 79622d32 6b206574
                03020100 07060504 0b0a0908 0f0e0d0c
                13121110 17161514 1b1a1918 1f1e1d1c
                09000000 4a000000 00000000 27594131

                 ChaCha state with the key setup.

  After running 20 rounds (10 column rounds interleaved with 10
     "diagonal rounds"), the HChaCha state looks like this:

                423b4182 fe7bb227 50420ed3 737d878a
                0aa76448 7954cdf3 846acd37 7b3c58ad
                77e35583 83e77c12 e0076a2d bc6cd0e5
                d5e4f9a0 53a8748a 13c42ec1 dcecd326

                   HChaCha state after 20 rounds

  HChaCha20 will then return only the first and last rows, in little
     endian, resulting in the following 256-bit key:

                82413b42 27b27bfe d30e4250 8a877d73
                a0f9e4d5 8a74a853 c12ec413 26d3ecdc

                    Resultant HChaCha20 subkey

From the above example it looks like what HChaCha20 should return is an array of little endian integers, but why is it swapped in the end ? Didn't we consider the nonce, key, counter everything as little endian in the first place !? Why do we again make it little endian again if we are returning an array of uint32_t integers (which are by default little endian on my platform), or is the author referring to converting the array to byte string (unsigned char array) ?  Please do clarify where I went wrong... Every help will be appreciated!


texts: Using division polynomials to prove that EC discrete log is even

texts:
This question is related to the other question I recently asked. I'm trying to figure out if it is possible to use division polynomials to prove that knowing $A = a \cdot G$ we can prove that $a$ is even without disclosing the value of $a$.

One useful property of division polynomials that I've observed is that:

$$
\psi_{nk}(G) = \psi_k(G)^{n^2} \cdot \psi_n(k \cdot G)
$$

For even division polynomials this can be re-written as:

$$
\psi_{2k}(G) = \psi_k(G)^4 \cdot \psi_2(k \cdot G)
$$

If we define $a = 2k$ and $A' = A / 2$, and assuming coordinates of $A'$ are $(x_{a'}, y_{a'})$, we can re-write this as:

$$
\psi_{a}(G) = \psi_k(G)^4 \cdot \psi_2(A') = \psi_k(G)^4 \cdot 2y_{a'}
$$

Using this we can prove that $a$ is even by doing the following:

Prover computes $s = \psi_{a}(G)$ and $v =\psi_k(G)$ and shares $(s, v)$ with the verifier.
The verifier computes $A/2$ and verifies that $s = v^4 \cdot 2y_{a'}$

Are there any flaws in this approach?


texts: Does there exist a mode of operation that forces mac-then-decrypt?

texts:
Alice sends Bob a message using AES-GCM. Bob is a software developer with just enough cryptography knowledge to be dangerous. He wants to start processing data as soon as he receives it. He observes that he can ignore the tag and just decrypt the CTR-mode ciphertext.

In every mode I can think of it is possible to decrypt a message without performing the authentication part. Does there exist a standard or named mode of operation that makes it impractical to try to skip or defer authentication?

It seems like such a scheme would necessarily be two-pass. It's fine if the first pass is always authentication and the second pass is decryption.

I had two (incomplete) ideas for how such an encryption scheme might work. I include their descriptions because it might aid to better explain the question asked above.

My initial idea involved first encrypting plaintext using an unauthenticated algorithm and random IV. Then the ciphertext would be fed to some kind of HMAC. The first 128 bits of HMAC output would become the message tag. The remaining bits would not be published and instead be used as a tweak for encrypting the IV.

(This prevents the recipient from decrypting the message without first performing the MAC algorithm because otherwise the IV remains unknown to the recipient. One issue is that the IV isn't authenticated.)

My second idea was to try adapting an all-or-nothing-transform, "an unkeyed, invertible, randomized transformation, with the property that it is hard to invert unless all of the output is known."


texts: How to get the order of a group generator in DH?

texts: For a DH parameter prime, if the generator $g$ is 2, how do I get the order $q$?


texts: RSA Question- max number of ascii characters encrypted at one time

texts:
I'm a student new to cryptography and have a fairly straight forward RSA question that I'm struggling to wrap my head around.

"Alice's RSA public key [N:e] is stored in binary as a 16bit integer &: 8bit integer.

What is the maximum number of ASCII letters that can be encrypted at once and sent to Alice if assuming no padding?"

My initial thought was 1 ASCII character at a time because M < N. Therefore it couldn't be 2 characters (2 x 8 bits) because M would = N.

From my understanding of modular arithmetic:
51 mod 5 = 0   But    41 mod 5 = 4

So I kind of understand that if M is equal or greater than N, I will only decrypt an equivalent message but not identical.

Could somebody explain this to me in more detail?


texts: Is a one-time pad secure if the encryption method is not?

texts:
(The following situation is hypothetical.)

I need to communicate something securely and I have decided to use one-time pads.

I am going to be using human genes as the source of the OTP data (this is important).

If I were to use (for example) a weak kind of encryption, in this case a variation of XOR 'encryption', would the fact I am using OTPs offset the weakness of XOR 'encryption' or would it be a complete waste of time because XOR is still inherantly weak?

If it matters, before being XOR 'encrypted' the messages will be plaintext in an unspecified human language (English, Japanese et cetera - the language is irrelevant other than being a known, well spoken human language).

Disclaimer:
I won't be offended if I'm told that this is a horrible idea - It's not my idea.


texts: Is it a good idea to use bitwise XOR on a set of MD5 sums?

texts:
I have designed an SQL aggregate function in Oracle that bitwise XORs all MD5 sums of the values stored in a column.

For example, if my table is:

+-----+----------+---------+
| Key | Sequence |  Value  |
+-----+----------+---------+
|   1 |        1 | 'Hello' |
|   1 |        2 | 'World' |
|   2 |        1 | '1234'  |
|   3 |        0 | (empty) |
|   4 |        1 | 'Hello' |
|   4 |        3 | 'World' |
+-----+----------+---------+

I can run the following query in Oracle:

with t AS (select 1 key, 1 sequence, 'Hello' value FROM dual
           union all select 1, 2, 'World' from dual
           union all select 2, 1, '1234' from dual
           union all select 3, 0, '' from dual /* ... */
          )
   select key, md5_agg(value) from t group by key

and get (unfortunately aggregate functions in Oracle ignore NULL values and '' is considered as NULL)

+---+----------------------------------+
|key| md5_agg(value)                   |
+---+----------------------------------+
| 1 | 7EBD0B1DA67F965F802D31DF25C4B321 |
| 2 | 81DC9BDB52D04DC20036DBD8313ED055 |
| 3 | 00000000000000000000000000000000 |
| 4 | 7EBD0B1DA67F965F802D31DF25C4B321 |
+---+----------------------------------+

I would like to use this approach to compare if the contents of some columns are equal when I compare subsets of the same table (think of finding duplicates in a complex structures that spans over multiple rows in the same table). Here with this results I know that I have the same subsets for keys 1 and 4.

What are the limits of such an approach? Here are the ones I could list:

This is interesting only if my column contains distinct values. If my columns contains twice the same string, the xor operation will be a no-op.
Due to Oracle limitations, if my column contains empty values, they do not count.

With those limitations in mind, is it still possible to infer, from two equal md5_agg results computed from distinct and non-empty values, that the original values make up the same sets?

In order to reformulate, are there odds that the MD5 sums of distinct strings XOR to 0?


texts:
I have a point $(X,Y)$ on an elliptical curve $E(a,b)$ where $a=-3$ and $B$ is a large number that is in hexadecimal from -51BD. To compress this point oficially in a program, we know that every $X$ on the curve has two $Y$'s, one even and one odd. Therefore, we only need to store whether the corresponding $Y$ point we are storing is even or odd. So to store the point $(X,Y)$ now, we shift $X$ ridding of its most significant bit and add $1$ if the $Y$ point is odd. Therefore, one can think of the compressed point being $2 \cdot X+B$ ($B$ is the bit we added to tell if $Y$ was odd or even) since the multiplication by $2$ is implied because of the shift. I understand this completely. It's recovering the original point that has me confused.

Since a point on the curve is given by the equation $y^2=x^3+ax+b$, we can find square roots officially in $\mathrm{GF}(p)$. The following from my spec is what confuses me.

If $p$ is prime and congruent to $3$ mod $4$, one of its square roots is $z^{(p+1)/4} \bmod p$ and the other is $p-z^{(p+1)/4} \bmod p$. How would I solve this? What is $z$?

For example, I know how to extract the $x$ point so let's say I simplify the right side of the equation to be $7$ and $p$ is $11$. Would I be trying to solve for the square root that's equal to $7$ mod $11$?


texts: Can I use a differential that can be traced through the whole cipher with 100% probability?

texts:
I'm trying to attack a very simple cipher using differential cryptanalysis as a way of becoming familiar with this method. The cipher is so simple that I've found a differential which I can trace through all the rounds of the cipher with 100% probability (it is not 0 of course).

I've read/watched a few tutorials and if I've understood them correctly recovering the last subkey works as follows:

Find $\Delta_X$ which you can trace with high probability.
Choose two plaintexts such $X_1$ and $X_2$ that $X_1 \oplus X_2 = \Delta_X$
Encrypt them, getting $Y_1$ and $Y_2$.
Try to brute force last round's key. For each key: Decrypt the last round for both ciphertexts, getting $Z_1$ and $Z_2$. If $\Delta_Z=Z_1 \oplus Z_2$ is the same as you predicted form $\Delta_X$ the key can be correct. It gets one point.
Repeat it for different plaintext pairs.
The key that has the highest score is probably the correct one.

Maybe I've misunderstood something about DC, if so, the remainder of this question is probably nonsense. That's why I've described what I think differential cryptanalysis is.

But if it's correct:

Key doesn't influence the differential (it holds with 100% prob.) so whatever key I try while decrypting the last round, the differential on it's input is always as expected. Thus I can't eliminate any keys.

This seems suspicious to me - if a differential holds with 100% prob. the cipher is weak, right? Can a cipher be so weak that some attack doesn't work on it? It seems quite strange...


texts:
To my understanding, there are two "approaches" to t out of n threshold encryption. In both of them, n shares are given to different shareholders, and at least t of them must agree to "proceed". "Proceed" can take two different meanings: either the shares are the input to derive a secret that can be used to perform a traditional decryption (e.g. Shamir) or the shareholders produce a partial encryption that can be put together to generate the decryption (e.g. Damgård-Jurik).

I have found the first scenario to be known as secret sharing, but I am looking for a term to describe the second approach unambiguously. Does such term exist?


texts: Does this equation hold in a bilinear map?

texts:
I would like to verify whether or not the following equation holds:

$e(a,c)^{c1\cdot c2\cdot c3}e(b,c)^{c1\cdot c2\cdot c4}==e(a,c)^{c2\cdot c3}e(b,c)^{c1^2\cdot c2\cdot c4}$ for appropriately defined bilinear map $e$ with different input groups $G_1$ and $G_2$ for $a,b\in G_1$ and $c\in G_2$


texts: Could a key derivation function be used to encrypt data with a weaker key?

texts:
To allow the key to be more easily remembered.

Example:
To encrypt a hard drive without having a remember a key with 128 bits of entropy.

From what I find they seem mostly used to hash passwords so the password database is more resistant to brute force in the case it's compromised. (compared to using a regular hash function)

So I'm not sure that the use case that I mentioned would be safe.


texts:
I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis.

Beside the key lenght I know there are some weakness in the choice of prime numbers that could help an attacker to factor the modulus $N$.

The standard key generation, as far as I know, generate a random number of the right lenght, tries to factorise it dividing it by small factors (say $\leq 10000$) and then one or more primality test (as Fermat and Miller-Rabin) until the confidence level is high enough.

But what about risks that $p-1, q-1$ are with small factors?


texts: What guarantees that a mined block will be accepted on the network? (Blockchain)

texts:
What ensures that a mined block will be accepted on the network? I mean, if I mine a valid block in the blockchain, and I transmit it to the network, what is the incentive to people accept it? Doesn't may happen a case where I mine a valid block and it get's refused?
And the reverse case, what ensures that if I mine a invalid block that this will be rejected by the network?
Just asking some newbie questions about it.


texts: Understanding pseudo-random functions (used in a Oblivious Transfer Protocol)

texts:
Given a family of pseudo-random functions

$$\{F_K:\{0,1\}^m\mapsto \{0,1\}^m | K \in \{0,1\}^t \}.$$

I want to understand how the elements behave.

Lets say we take some $F_{K_1}$ and evaluate at $x=(0,\dots,0)\in\{0,1\}^m$, is it true that the evaluation of $F_{K_1}$ at $x$ always yields the same result? Why property does make this set so special? I tried to understand the definition from wikipedia, but failed to do so..

I am asking this questions and trying to understand PRF because I am studying a paper about generalized OT protocols which can be found here ( page 5).


texts:
I've been reading a lot about techniques related to stylometry whereby programmers can be de-anonymized by analyzing their source code.
Resisting deanonymization seems like a multifaceted problem. From variable renaming, space generation etc... to structural changes such as loop re-writing, function splitting, etc...
It seems very similar to the problem of obfuscation, but the goal is not to make the code unreadable as much as unattributable.
I was curious if there has been any serious research into developing techniques into resisting stylometry, and what they look like?


texts: reverse an identicon to its source string

texts:
Identicons are used to create unique images based on IP address or strings. Lots of programs are available to generate identicons based on an input string.

My question is how hard is to do the reverse. Identify the source string of an identicon. In other words what is the strength of the hash function used to generate an identicon.

Can the concept of identicon be extended to generate public-private key pairs? It would be lot attactive to have two images as public and private key rather than a boring text file


texts: Cryptographic random number on interval $[0,n]$ from bytes

texts:
I really like this answer: Creating a small number from a random octet string

While this works, is it safe to generate random number like so?

I am looking for a number on interval $[0,203]$
Generate crypto random secure 8 bits
convert to a decimal variable $d$
final answer $=\frac{d}{255}* 203$

Is this safe and does it work?  Is it better or worse (maybe performance wise) than the answer in the other SE post?


texts: Calculation of the avalanche effect coefficient

texts:
Given a strict avalanche criterion matrix/dependence matrix for a hash function,how do I calculate the avalanche coefficient for it. I want to calculate a single parameter(value) which represents the amount of avalanche effect for the given hash function.

I have thought of computing mean all over the matrix but am not sure that's the correct thing to do.

The following paper talks about the avalanche coefficient but they haven't mentioned the way they calculate it.


texts: How many repetition in Ciphertext-Only-Attack?

texts:
Given the following algorithm, how many times do I need to repeat step 2&3 to complete the attack? Please note that block size and key are 128 bits.
Step1: Prepare set S of size 2^k which contains all possible keys
Step2: Prepare 1 ciphertext C
Step3: Try to decrypt C using every key in set S. If the decrypted text contains characters that are not ASCII code, remove the key from set S
Step4: If only 1 element is left in set S, then that is the key used in encryption
My trial:
Possibilities of characters being not an ASCII code is 1/2.
Block size is 128 bits, which represents 16 ASCII characters. So, the probability of not having a single  ASCII characters is 2^(-16).
If we repeat steps 2 and 3 a times, the number of keys left in set S will be 2^(k-a16).
For the element left in set S to be 1, k-a16 = 0.
therefore, a = k/16 = 128/16 = 8.
I am not sure whether my answer is correct. Can anyone help? Thanks in advance.


texts: Is there an advantage to "weak" hashing and stretching over strong hashing?

texts:
Is there any sort of practical advantage to using a stretching algorithm such as PBKDF2 on say SHA256 over a straight SHA512 hash?

If the purpose of key stretching is to increase the length and thus prevent any shortcuts in cracking short keys, is there still a purpose when it is fairly easy to generate keys of lengths that make them close to impossible to brute force?


texts: How to securely and noninteractively generate a blinding factor in MimbleWimble Pedersen commitment?

texts:
I'm working on a prototype which will use MimbleWimble Confidential Assets transaction protocol using Cosmos as the blockchain layer.
In my prototype a user is always sending a whole amount to another user (so, one transaction has always one input and one output). Each user can have a public-private key.

How can a sender generate a blinding factor (r) in a secure and non-interactive way (so even a sender himself can't know the r and spend the receiver transaction)? What's the state of the art?
Additional question. If we don't record any addresses (so a transaction doesn't have any source account, only the commitments and range proofs), is the user anonymity preserved? So the external observer (assuming he can't link transactions with wallet IP addresses) will not learn anything about who is receiving the transactions.


texts:
It is obvious that changing even one bit in data or IV (initialization vector) will change the hash value a lot. I want to know if, for example, changing a single bit within the $IV$ in MD5 can be neutralized by changing the message data using a specific algorithm?
I think the differential attack on MD5 can be helpful but I don't know how?


texts: Fiat–Shamir: why do r and s have to be smaller than n?

texts:
I have a question regarding the Fiat–Shamir identification protocol. In this source (pdf) for example it says on pages 9 and 10 that the random commitment $r$ and the private key $s$ have to be smaller than $n$ (the RSA-like Modulus). I am wondering why this has to be.

The verification works even if $r$ and $s$ are greater than $n$. Also, if $r$ is smaller than $n$, an observer could calculate $r$, using the equation $y=r*s^e$ mod $n$. If $e=0$, this is equal to $y=r$ mod $n$, and since $r<n$, this is the same as $y=r$, so if somebody gets to know $y$, he would also know $r$. I thought that somebody was not supposed to be able to get information out of the knowledge of $y$ or $x$.

Is there something I am getting wrong here?


texts:
If I implement EMSA-PKCS1-v1_5 in the following two non-standard ways, what kind of things could go wrong?

The padding structure will be referred as (00|01|PS|00|DER(Digest Algo)|Digest), where | is concatenation and DER is DER encoding of an ASN.1 value of type DigestInfo:

DigestInfo ::= SEQUENCE {
  digestAlgorithm AlgorithmIdentifier,
  digest OCTET STRING}

I encode the structure as (00|xx|PS|00|DER(Digest Algo)|Digest) which means that I stored some data in the xx field (e.g., xx can be 01, 02, 03, 04). And I will check the xx value during the PKCS padding check, i.e., the xx value is also passed as plaintext for me to check against the ones in the encoding.
The digest is normally created using SHA-1 hash of data, e.g., Digest=SHA1(data). However, I split the data into data0 and data1 and create SHA1(data0) and SHA1(data1). So the Digest=SHA1(data0)|SHA1(data1).


texts: Reduction from integer factoring to computational Diffie Hellman

texts:
The computational Diffie Hellman (CDH) problem for ${\mathbb{Z}}^*_p$ is given a prime $p$, a generator $g$ of ${\mathbb{Z}}^*_p$, and a pair $(g^i, g^j)$ to compute $g^{ij}$. The value $g$ is called the base. In cryptographic protocols the base is usually fixed in advance.

This problem generalizes to other groups. For fixed $n$ a product of two primes ($n$ will always be a product of two primes) the composite CDH function is defined
$$ CDH: {\mathbb{Z}}^*_n \times {\mathbb{Z}}^*_n \times {\mathbb{Z}}^*_n \to\ {\mathbb{Z}}^*_n $$
$$ CDH(g,a,b) = \left\{g^{ij} : a = g^i \text{ and } b = g^j \text{ for } i,j \text{ in } \mathbb{Z}\right\}. $$
The composite CDH problem is to compute a value of this function.

One difference from CDH for prime moduli is that ${\mathbb{Z}}^*_n$ is not a cyclic group. I have called the first argument $g$ as an analogy to the prime case but it cannot be a generator of ${\mathbb{Z}}^*_n$.

It is known that factoring integers reduces to computational Diffie Hellman in the sense that if any instance of the CDH in ${\mathbb{Z}}^*_n$ be solved then the modulus can be factored1.

The algorithm is simple so I will summarize it. The only tool that's needed is a reduction from integer factoring to finding roots of quadratic binomials2. Of course factoring binomials is equivalent to finding $\sqrt{x}$ for $x \in {\mathbb{Z}}^*_n$.

Let $Q(n)$ be the set $\left\{a : a \in {\mathbb{Z}}^*_n \text{ and the multiplicative order of } a \text{ is odd} \right\}$.

The main idea for reducing factoring to CDH is that if we choose random $c$ in $Q(n)$, and a pair of integers $x_0, x_1$ and compute $c^{2x_0x_1}$ then two square roots can often be found using CDH. Let
$$ y = c^{x_0x_1} $$
$$ z = CDH\left(c^4, c^{2x_0}, c^{2x_1}\right) $$
then $y^2 = z^2 = c^{2x_0x_1}$. Since the choice of $c$ was random, $gcd(y - z, n)$ has a $1/2$ probability of splitting $n$.

One way to think about this reduction is if the CDH function can be computed on a non-negligible proportion of bases then we can quickly factor $n$.

Another way is that if the base $d$ used in CDH is fixed in advance then to use this reduction to factor we
need to find a root of the polynomial $f = X^4 - d$. As I said above, integer factoring reduces to finding (several) roots of a polynomial. So it is not surprising that knowing a single root of $f$ in addition to a CDH algorithm is enough to let us factor $n$.

It would be better to have a reduction that works independently of the base. Are any reductions like this known ?

Footnotes:

[1] Let $f = X^2 - a^2$ for random $a$ in ${\mathbb{Z}}^*_n$. By the Chinese remainder theorem $f$ has $4$ roots. Suppose we can find two roots $r_0, r_1$ with $r_0 \neq \pm r_1$ of in ${\mathbb{Z}}^*_n$. Then $r_0^2 = r_1^2 \bmod{n}$ so $\gcd(r_0 - r_1, n)$ is a factor of $n$.

[2] McCurley, K.S. A key distribution system equivalent to factoring. http://mccurley.org/papers/equiv.pdf


texts:
I want to implement a secure chat via mobile. I´ld like to know if the following protocol for key agreement – which can use any asymmetric encryption – exists.

Suppose Alice and Bob are two clients of the app. For this they have to register their public keys in a server:

Alice generates her public and private keys (pub_A, priv_A).
Alice sends pub_A to a public server.
Bob generates his public and private keys (pub_B, priv_B).
Bob sends pub_B to a public server.

Suppose A want to send a message m to B using AES:

The server generates a random symmetric key key_AES and encrypts it using pub_A and pub_B. Then it sends the encrypted key to Alice and Bob respectively.

Does this (chat) protocol for key exchange exist?


texts: What does it imply if in RSA pow(m, e, n) is same as the m

texts:
So, Let's assume we have n which is made up of 2 strong primes which cannot be factored & e which is textbook value of e that is 65537.

Now, I have a message1, first I convert that into decimal and then do

(msg1^e)%n and this turns out to be exactly same as random1 . Now, I generated a lot of messages and performed the encryption same way and I found one of the message (let's call it msg2) generates same output after encryption as it is in plain.

So, usually RSA formula is c=pow(m,e,n) . In my case pow(msg2,e,n) gives output exactly same as msg2. That implies for an edge case of a message the encryption provides same ciphertext as plaintext.

Does this means, that this RSA system for n is broken/buggy?


texts:
I have the following protocol for mutual authentication ($V=$ verifier, $P = $ prover, $r_V$ and $r_P$ random values, $h_k$ a keyed hash function)

$V\rightarrow P:r_V$
$P\rightarrow V:r_P,h_k(r_V,r_P)$
$V\rightarrow P:h_k(r_P,r_V)$

My question is why does the prover send back to the verifier $h_k(r_V,r_P)$? Can't he just send back $h_k(r_V)$? Or is this less secure.


texts: What is the original paper of the length extension attack on hash based MAC functions

texts:
A message authentication code (MAC) based on using a hash function with the secret prefix $H(k||m)$ technique goes back to two independent sources according to Tsudik's article on 1992;

S. Crocker, S. Kent, Private Communication, December 1990.
J . Galvin, K. McCloghrie, J. Davin, Secure Management of SNMP Networks Proceedings of IFIP Integrated Network Management Symposium, April 1991

The first real attack on the Merkle-Damgard construction is executed on the Flicker API

Flickr's API Signature Forgery by Thai Duong and Juliano Rizzo Published on Sep. 28, 2009.

Tsudik also mentioned the length extension attacks on the same article as;

Another curious property of the secret prefix method is its vulnerability to padding attacks5 (A padding attack is successful when the intruder is able to either prepend or append extraneous data to an authentic message and pass the resulting message off as genuine .)

and footnote 5 on the article is "This vulnerability was discovered by Dave Solo and Steve Kent"
This is not a real reference in the academic sense. When we look at the A. Menezes, P. van
Oorschot, and S. Vanstone's book, they wrote this ( referring 2. reference of the Tsudik );

Galvin, McCloghrie, and Davin suggest addressing the message extension problem in the secret suffix method by using a prepended length field (this requires two passes over the message if the length is not known a priori).

I couldn't find the article of Galvin et. al, only the patent application, to see that where they were referring. So;

What is the original paper of the length extension attack to refer academically?


texts: Extracting Randomness from a Poisson Distribution

texts:
I'm working on a quantum random number generator based on the shot noise of CMOS camera sensor. Shot noise in an image is caused by the variance of the number of photons hitting the sensor per unit of time. The distribution follows the Poisson distribution. To collect shot noise, I have to illuminate the sensor with a diffused light source.

A lot of papers discussing how to extract randomness from shot noise usually use equal frequency binning method. The following image is an illustration of randomness extraction using two bins. If the current sample is greater than average, output 1, if the current sample is less than average, output 0.

The problem with this method is it's not easy to determine the cut points, or in this case, the average. I tried to use moving average but the voltage of the light source sometimes drops for a few seconds caused by the other electronics in my room and it makes the output generated by my RNG sometimes biased for a few seconds. I tested the generated data using NIST Statistical Test Suite and it only passed 5/15 tests.

Although it passed 14/15 tests when I applied von Neumann debiasing method, the fact that the quality of the raw data is really bad still bugs me. So I experimented with a different extraction method. Here's how it works using one pixel

Let Brightness(t) be a function that returns the brightness of the pixel at time t

if Brightness(0) < Brightness(1) then
    output 1
if Brightness(0) > Brightness(1) then
    output 0
else
    don't output anything

Basically, take two non-overlapping samples, if the second sample is brighter than the first one, output 1, if the second sample is darker than the first sample, output 0.

The data generated using this method passed 15/15 NIST tests. But since I've never seen any paper discussing a method like this, I need confirmation if this method really as good as it looks, and maybe some explanation why it's good. Thank you.


texts: What is the difference between Shannon entropy and saying that tossing a 6-sided die 100 times has more than 256-bit entropy?

texts:
I'm confused.

I thought that tossing a 6-sided die 100 times had a greater than 256-bit entropy because $6^{99} < 2^{256} < 6^{100}$. (A similar concept appeared in this XKCD comic, where choosing four random words from a dictionary of presumably 2048 words has a 44-bit entropy, presumably because $2048^4 = 2^{44}$.)

On the other hand, the Shannon entropy of a 6-sided die tossed 100 times is $-6 × 1/6 × \log_2(1/6) = 2.5849625007$ bits. (According to the comments by Sakamaki Izayoi to my other question.)

Are these two different concepts of "entropy" entirely? If so, what's the difference and if not, what am I missing?

I read this thread but I'm still confused.


texts: Reason for difference in assumptions for practical private-key and public-key crypto

texts:
Theoretical cryptography tells us that everything in the world of private-key cryptography (CCA-secure symmetric encryption, message authentication codes, etc.) can be built from one-way functions and that public-key cryptography (e.g., CCA-secure public-key encryption) can be build from the stronger notion of one-way trapdoor permutations. In addition, it is known that both one-way functions and one-way trapdoor permutations can be built based on certain number-theoretic assumptions such as the hardness of integer factorization and the discrete log assumption.

In the case of practical private-key cryptography, however, constructions are almost never based on number-theoretic assumptions, but rather on much more "high-level" assumptions, for instance the assumption that AES is a pseudo-random permutation (here I'm ignoring some technical details, e.g. that a pseudo-random permutation must be defined for infinitely many key sizes, at least to be secure in an asymptotical sense).

In contrast, all known public-key constructions (including those used in practice) seem to be based on either number-theoretical assumptions (e.g., RSA, DDH) or, in a few cases, assumptions regarding linear codes or ideal lattices - all of which seem rather "low-level" compared to e.g. the AES or DES assumptions used for private-key schemes.

This seems to explain why the public-key crypto schemes used in practice today are orders of magnitude slower than the private-key schemes used in practice.

Is there any explanation for this difference in the level of assumptions underlying the private- and public-key crypto schemes used in practice today? Is this due to historical reasons, or is there some other, perhaps mathematical, reason why no efficient public-key schemes today are based on assumptions on a similar high level as e.g. the AES? Have I missed some fast public key encryption schemes based on assumptions on such high level?


texts:
I am using a PGP method to encrypt and decrypt messages shared between users A and B.

Upon the start of a message exchange is the initialization of the public and secret keys by both Users.

Lets say that User A downloads the message exhange app and he adds his friend (through phone number). He then wants to initialize a conversation. At this point User B has still not downloaded the app.

How are the keys to be safely generated if it is User A initializing the conversation? Technically, the request of creating the secret key for both parties would then have to be done by User A as well, which makes it not safe.

Without the public key of User B (thus also the creation of the secret key for User B), User A will not be able to start sending encrypted messages.

The obvious solution is that he will need to wait before the friends accepts the friend request, thus creating and sharing the keys.

Is there a way to solve this issue without this restriction? That is, how can User A already start sending encrypted messages to User B, who has not signed up and accepted the request?


texts: In differential cryptanalysis for DES, why is F(0...0) assumed to be always 0...0?

texts:
In this paper about differential cryptanalysis, an attack on 2n-Round DES is described.

The attack is all about finding certain inputs for DES rounds, for which the output of the round function Fis equal to the input with high probability.

For the inputs given in the paper, one half is always assumed to consist of only zeros. Also, it is assumed that the round function for that all-zero input always yields zero with probability one:

F(0...0) = 0...0

To my understanding the round function F works as follows: Expand the input, then xor the key, then perform substitutions. That conflicts with the assumption described in the paper.

How can the round function always yield zeroes for an all-zero input, independently of the key?


texts:
DJB described curve25519 in his paper which can be found here (PDF). It seems that the main purpose was for Diffie-Hellman key exchange. I think this means that Discrete Log is supposed to be hard on curve25519.

My questions is whether DDH (Decisional Diffie-Hellman) assumption is conjectured to hold on curve25519 too so that we can use it for building an ElGamal encryption scheme. Some quick investigation shows that DDH are assumed to be hard on elliptic curves with large embedding degree (Wikipedia – Decisional Diffie–Hellman assumption) and it seems that most elliptic curves have large embedding degree except those constructed for pairing based crypto.

So, I guess the answer should be “yes”. But still I would like to get some expert knowledge to confirm that one can securely build ElGamal encryption on this curve.


texts: Offline Complexity of the garbling scheme

texts:
The offline complexity of the garbling scheme means the time complexity of the circuit encoding algorithm, that is, $\textrm{GC.Circ}(1^\lambda, C)$, where $C$ is the circuit to be garbled. It's straightforward to see that the offline complexity is $\textrm{poly}(\lambda, C)$.

My question is that whether there exists any optimal offline complexity of circuit encoding algorithm? for example, is it possible that the offline complexity is "sublinear" in the circuit size?


texts: Is RC4 cipher just xoring plaintext with a random sequence seeded by key?

texts:
After reading about RC4, it seems that it's nothing else than:

the plaintext stream is just XOR'ed with a pseudo-random sequence that
is initialized/seeded with the key

Is there something else in the algorithm?

Is there a general name for stream ciphers that use a XOR with a (pseudo-random) sequence seeded by key?


texts: How to test the robustness of the cipher image against chosen and known plaintext attacks?

texts: Is there any algorithm to test the robustness of the cipher image against chosen and known plaintext attacks?


texts: If someone had a list of all primes, would it be possible for them to factor any integer in polynomial time?

texts: For example, if they somehow got a function that would churn out any arbitrary amount of primes in a row. Could they break the RSA problem then?


texts:
I'm planning to use the crypto_box() functions of Nacl (or, alternatively, the crypto_box_easy() functions of libsodium) to encrypt messages as part of a client/server protocol. The server has to deal with multiple clients and each message from a client to the server is encrypted using the public key of the server and signed with the private key of the client.

The cypto_box() functions also require me to provide a nonce. The current message number could be used as a nonce–to my understanding, the nonce is necessarily known to an attacker who is capable of keeping track of how many messages were exchanged. Both, the client and server would then maintain a message counter and simply use the newest counter value as a nonce.

However, I must deal with the case where messages are reordered or lost. Therefore I'd send the nonce in plaintext alongside the encrypted message. As long as the same nonce is not used twice, I don't see any problems with this approach. Did I miss out on something?


texts: Is text description of MD2 algorithm wrong?

texts:
I'm trying to implement MD2 from scratch of RFC 1319. It feels like there is a gap between steps 3.2 & 3.3.

After step 2, the checksum C is appended to the message and never mentioned again. We start 18 rounds of XOR-ing for each block using MD buffer X, which will contain the final result.

But when I look at most MD2 implementations, it looks like the checksum serves as an internal state of the algorithm and being re-calculated during each block processing, e.g. in this Rust implementation.

Is it implied somewhere in the description or pseudocode?


texts: Will reading "Elementary Number Theory" by David M. Burton be useful for Cryptography?

texts: I am a Computer Science student and interested to learn Cryptography to be a researcher in this field. I heard that Number Theory is useful for Cryptography since there are some Crypto systems based on it. I really like Number Theory and have started reading Elementary Number Theory by Burton. So far I have been reading the theorems and trying to prove them myself. Will my approach be useful for Cryptography?


texts: A website that identifies an RNG from its output

texts:
This happened during a discussion of RNG entropy, and the difficulty of verifying the level of entropy in a long sequence of bits (e.g. a private key.)

A colleague of mine told me about a website that, given a sufficient quantity of output from an PRNG, had been able to deduce which application the PRNG was from. As an example, he told me that he had submitted data from OpenSSL's random number generator and the website had identified "Open SSL" as the source.

This was about three years ago. He encountered the website at a previous company he worked at.

I can't find this site by googling, and my colleague may not be able to find the URL (he's looking it up.) Not surprisingly, I'm very worried if the output from supposedly-cryptographically-secure-PRNGs is vulnerable to a distinguisher attack with trivial complexity!

If anyone here recognises this website, could they please post an answer containing its URL?


texts: Using rainbow tables to find encryption keys of block ciphers?

texts:
Hi I have a question in mind.

  Let's consider a block cipher whose key length is 36 bits.
  The bit-length of the plaintext is 256 bits, but there are only 16 possible plaintexts $m_0, m_1, . . . , m_{15}$. The encryptions are carried out in ECB mode and thus no IV is involved. We want to build a rainbow table such that, on input a ciphertext, we can readily find the key and the plaintexts.

How do we go about constructing a rainbow table for this purpose?


texts: RSA-OAEP versus RSA with Fujisaki-Okamoto construction

texts: I was wondering why the Fujisaki-Okamoto construction (or one of its variants) is not (at least commonly) used with RSA to achieve CCA2 security? Does anyone know of any speed comparisons between RSA w/ F-O and RSA-OAEP? Perhaps the reason is simply historical since F-O is newer.


texts: Determining the degree of freedom for a chi-squared test on a strict avalanche criterion matrix

texts: I have read that the degree of freedom is calculated by subtracting 1 from the number of states a random variable can be in. I am performing a goodness of fit test on a 64*32 strict avalanche criterion matrix where the expected frequency of any a[i,j] is 50000 and the observed frequency can lie between [0,100000].What I am confused about is that how do I calculate the degree of freedom? Since the observed value might range from 0-100000, will my degree of freedom be equal to (100000-1)? Please advise.


texts: Can public key help attackers to break RSA encryption faster?

texts:
I have two, closely related questions:

Can a really good attacker (hacker) use the public key for his advantage and break RSA encryption faster? My point is that in RSA "communication" public key is moving from server to client… If attacker will get this key and also encrypted data will be there any advantages or it is not important if attacker has public key?
If, for example, there are five users and each user has public key but with different size (2048, 2100, 2120,2250,2310bits etc.) If attacker will break one of these key all other keys are also immediatelly know for this attacker or he must start whole process of breaking again? Is there some advantages to have each RSA key with different bit size?


texts: How is formal analysis of the strength of a round achieved?

texts:
I've been trying to understand how the number of rounds are picked for ciphers.  There seems to be a minimum number of rounds that is analyzed for "strength" and then some security margin is added.

M. Luby and C. Rackoff showed that you need only three rounds for a Feistel network if you have sufficiently random keys; however, this is not practical in reality, which is why we have key expansions.  This leads me to my questions:

How is the strength of a key schedule formally analyzed?

We have suites for random numbers, such as diehard, but I've not found a reference how key schedule strength is formalized.  One could look at series of rounds through diehard, but the keys will obviously be related.  Furthermore, in literature, generally it seems that the key schedule is the most ridiculed part of every cipher.  I dug into Ph.D. dissertations but I didn't find anything.  Any suggestions would be greatly appreciated.


texts: When it is safe to reuse IV? (or not using at all)

texts:
This is my case:

I don't have padding oracle (the server provide the data and users never able to execute the encryption function),
I never encoding the same text twice.
The text is always short - 128 bytes.
I store the encrypted text in the database.
I never send the decrypted text to any user.

What I want:

If one of the users have a copy of the database, he will never be able to decrypt the text.
If an attacker successfully accesses to one the text decrypted, it's a problem exactly like he has access to all the text decrypted.

In my case, is it safe to use AES-CTR with fixed IV (or not use IV at all).

In other words: If an attacker doesn't have any decrypted text, he has ONLY a database of unique 100k+ encrypted texts that use the same key and IV. Will he be able to break the encryption?

Please don't tell me about best practices, and Do not invent the wheel. I'm here to learn, and I want to know if there is REAL problem with using fixed IV or not use at all. I found that it is simpler to store in the database only one value, without saving IV for each value.


texts: Difference between Zero Knowledge Range Proof (ZKRP), Zero Knowledge Set Membership (ZKSM) protocols and ZKP

texts:
Like to know the difference between Zero Knowledge Range Proof (ZKRP), Zero Knowledge Set Membership (ZKSM) protocols and ZKP?

Nathan Aw


texts: Most Compact Secure Post-Quantum Signatures and Public Keys?

texts: Which post-quantum public key and signature system includes the most compact reusable keypairs?  E.g. a private key which produces practically unlimited signatures without losing the security provided initially like RSA as opposed to something like hash-based Merkle tree driven signatures with a limited number of uses?


texts:
I am using ABE scheme that has already proven under BDHE assumption. Here is the scheme https://eprint.iacr.org/2008/290.pdf

In the key generation algorithm, I want to tie the user secret key components with a message $m∈GT$. $m$ is different from the one used in the encryption algorithm.
I did like this

$S=M.e(g^t, g^d) = M.e(g,g)^{td}$  where $t,d∈Z$ are randomly chosen.
$t$ is used to tie all other secret key components together.

$S$ will be given to the user along with the secret key which have these components $(K=g^bg^{at}, L=g^t, h1^t, h2^t, …)$

$d $ and $g^d$ will be kept secure with the authority.

My question, do I need to re-prove the security of the scheme considering $S$


texts: It is possible to achieve the avalanche effect in an SPN or in a Feistel network that use a single round of an SPN in his function (like DES) using SBOX that receive 2 bit in input and output 2 bit?