texts: Hash function for a small, enumerable set of elements

texts:
Suppose you have a set of elements, that is relatively small (e.g. 100M) and its elements can be easily enumerated. For example phone numbers, that have a maximum fixed length and they are composed of only digits.

I would like to find a way for parties involved in an open communication to reference to elements without mentioning them in cleartext, so that only who "knows" a given element can understand that a message is referring to it.

For example, if elements would be arbitrary large files, parties may identify them by MD5 or SHA1 and communicate mentioning the hashes. Only the party that has the same file may understand that a hash actually refers to that file. This is based on the difficulty to invert the hashing function and to the fact that the set arbitrarly large files is almost infinite.

This mechanism however doesn't seem to work well when the set of the elements is small and enumerable.

QUESTION: do you envision another pattern the parties can implement to openly communicate and reference to the shared elements, without revealing their value?


texts: If someone finds an efficient way (ridiculous or not) to turn NP into P (such as creating multiple universes, saving the one with the correct answer), would we have any good algorithms for encryption, hashing and so on that are still secure? What other algorithms would become way more efficient? Constant-time sorting? Constant-time SHA256-cracking?


texts: How fast is hashing and is it always regarded as an O(1) operation?

texts:
I've wondered how hashing can be such a fast operation. It's so fast that nobody talks about it in terms of performance and complexity.
I know that in terms of big O notation, you can drop all the constants and just speak in terms of the variables. I know that in hash lookup, if you know the key, it is O(1). This makes sense to me. What didn't make sense was to get the message digest, you have to actually run the hash function, and nobody talks about this. What if the file or document is super large, the complete works of William Shakespeare. Does that take 1000x as long to hash as a one page document? I assume the hash functions have to run through every single bit of the data one by one, so doesn't that factor into time complexity? Maybe it doesn't have to run through every bit. Maybe it runs through every 8 bits or 32 bits or whatever a word size is in a system. I know bitwise operations are significantly faster and I know the SHA algorithms make use of them, but still, when people say hashtable lookup is O(1), I'm amazed at how the hashing itself can always be considered as nothing, regardless of file size, as it seems that the entire data would have to be traversed through.


texts: Breaking RSA, given a special kind of oracle that decrypts related ciphertexts for us

texts:
Let $c=E^{RSA}_{e}(w)$ be the ciphertext belonging to the plaintext $w$ if an $RSA$ system is used. Assume that the public exponent $e$ satisfies $e \le 10$. Furthermore, assume there is an oracle that, on input $r>0$, responds with the value $c_{r}= E^{RSA}_{e} (w + r)$.

Can the plaintext be decrypted efficiently, given this oracle?


texts: Why is the signatureAlgorithm field in X.509 certificates redundant?

texts:
See the ASN.1 description of an X.509 certificate below:

Certificate ::= SEQUENCE {
    tbsCertificate      TBSCertificate ({ x509_note_tbs_certificate }),
    signatureAlgorithm  AlgorithmIdentifier,
    signature       BIT STRING ({ x509_note_signature })
}

TBSCertificate ::= SEQUENCE {
    version           [ 0 ] Version DEFAULT,
    serialNumber        CertificateSerialNumber ({ x509_note_serial }),
    signature       AlgorithmIdentifier ({ x509_note_pkey_algo }),
    issuer          Name ({ x509_note_issuer }),
    validity        Validity,
    subject         Name ({ x509_note_subject }),
    subjectPublicKeyInfo    SubjectPublicKeyInfo,
    issuerUniqueID    [ 1 ] IMPLICIT UniqueIdentifier OPTIONAL,
    subjectUniqueID   [ 2 ] IMPLICIT UniqueIdentifier OPTIONAL,
    extensions        [ 3 ] Extensions OPTIONAL
}

What's the difference between Certificate.signatureAlgorithm and TBSCertificate.signature?

They appear to have the same value, and Certificate already includes a TBSCertificate in it, so one of the values is redundant.

Why is it included then?


texts: What basic knowledge is required to understand SIKE?

texts:
I'm interested in learning about Supersingular Isogeny based Key Encapsulation mechanism.
Currently, I only know all the basic knowledge about how standard Elliptic Curve Cryptography,  works, using Weierstrass equations. This includes the the mathematical group structure on how the Elliptic curve points are defined, and operations like point doubling and addition. I also learned how to implement it in C , with parameters of cryptographic size.
Since, SIKE is dependent on Elliptic curves, and mapping between curves, I'm guessing that my basic knowledge of how Classical Elliptic Curve Crypto works, would provide me (a beginner) some vantage point to begin understand how SIKE takes off from the ground up.
I realise, that the security of SIKE is not dependent on the classical Discrete Logarithm problem.
I cannot find online material, that presents SIKE and the mathematical basis required for it for a beginner.
Even, if that's not the case, I'm willing to learn the math required from the ground up.
Every, help will be greatly appreciated!
Thankyou, everyone in advance!


texts: When we turn Random shuffle to Pseudorandom Shuffle

texts:
It's well known that a simple but efficient random shuffle algorithm

can permute a vector of $n$ elements in $O(n)$ time.

In the algorithm, we need to pick a value $U$ uniformly at random where $0\leq U\leq 1$.

However, I need a pseudorandom function (or algorithm) so I can re-generate the same permutation over again.  Thus, I need to use a pseudorandom function to generate $U\hspace{-0.02 in}$.  But the pseudorandom functions usually output an integer but not value $U\hspace{-0.02 in}$, where $0\leq U\leq 1$.

Question:  How can we turn the random shuffle into a pseudorandom shuffle?

or

How can we map the output of pseudorandom function to a value in the interval $(0,\hspace{-0.05 in}1)$

such that the value in that range still is a pseudorandom value?


texts: why people don't use the same generators?

texts: i want to make many pederson commitments $C=g^s h^r$ for a long time , do i have to change the generators $g$ and $h$ or its ok if i always used the same ones


texts:
I'm currently writing my own implementation of Diffie-Hellma n(This isn't for actual use. This is strictly for me to get a better understanding of DH by doing it myself.)
For the prime and generator, I am using RFC 3526, more specifically the 4096-bit prime.
My question is, is there a specific standard secret integer generation for Diffie-Hellman? Since the security of the secret integers(Commonly two, but DH does support more than 1-1 communication) is pretty crucial to the security of the key exchange.


texts: Security of a custom non linear hill cipher

texts:
Initially let me state that this is an atypical type of cryptographic encoding.  First I break up my key into three parts $k = {W,\overrightarrow{b},\alpha}$. the $W$ is simply a $n \times n$ matrix, $\overrightarrow{b}$ is a vector of size $n$ and $\alpha$ is a scalar. My message is also a matrix with dimensions $k \times n$ I define my encoding as

$E_{W,\overrightarrow{b},\alpha}(M) = [\sigma^{\alpha}(W \cdot M^T + \overrightarrow{b})]^T$

$\sigma = \frac{1}{1 + e^{-x}}$

The addition of the vector occurs element by element per column and this is mapped to every column (essentially a linear transformation occurs per element in the message matrix). After that a sigmoid function to the power of $\alpha$ is applied to every element. Does this encoding still suffer from the known-plaintext attack or does the non-linear function deal with that? And is their any other known weakness to this encoding?
Thank you in advance.


texts: Secure way to store fixed size string of digits

texts:
I need to store a string of digits (0-9) of a fixed size in my database securely.

I've already performed a rainbow table attack on a plain hash, and it broke it in a matter of seconds.

One option I had was to break the string into 2 or more parts and store them separately, within reason (i.e do not have the resources for multiple servers), but I feel like this will only delay an attacker a small amount.

The other option is using salted hashes, but I'm not sure if this will help in this case.

Does anyone have any suggestions?


texts:
Wikipedia article on Montgomery modular multiplication contains the following statement:

  Many operations of interest modulo $N$ can be expressed equally well in Montgomery form. Addition, subtraction, negation, comparison for equality, multiplication by an integer not in Montgomery form, and greatest common divisors with $N$ may all be done with the standard algorithms.

My question is about

  greatest common divisors with N

It is clear that $(a,N)=(\mathrm{Redc}(a),N)$ since $\mathrm{Redc}(a)=aR^{-1}\mod N$ and $(R,N)=1.$ But the following thing is not clear.

Q: Are their any non-trivial algorithms based on Montgomery arithmetic which allow to find $(a,N)$?


texts: Can high-entropy data be reconstructed from plaintext XORs in CTR nonce reuse?

texts:
(My interest is academic; I certainly have no intention of rolling my own crypto, especially the known-broken type!)

I know that if the nonce gets reused in a CTR stream, the two cipher blocks can be XOR'ed together to produce a XOR of the plaintexts. From there, the plaintext is recovered using analysis, such as searching for words. This makes unathenticated memory encryption, used in practice, insecure against someone who can edit the counter and trigger reuse.

But my understanding is that such analysis is enabled by the very low entropy of sample plaintexts - the usual examples are English text or bitmap images, which only use a small fraction of the block's information capacity.

Since txt files and bitmaps are relics at this time (easily found in OS files, though), could the attacker still recover the key from XORs of higher-entropy plaintexts in modern data formats?

Specifically to consider .docx, which is compressed with zip (weak compression), and lossy-compressed images or video (high entropy, but they include structure and headers, and can be useful even if severely damaged).

What if the nonce was reused many times, giving the attacker a much larger amount of information? I have a feeling that there might be some mathematical limit, e.g. best-case plaintext recovery requiring at least 1-(1-(entropy/Shannon_limit))^number_of_pairs>entropy/Shannon_limit.

But no idea if that holds, or if there are techniques to reconstruct plaintexts from XORs of general-case data, rather than specific kinds such as natural language.


texts:
Having two known constant A and B, and one unknown X, can we solve the following equation :

(A xor X)+ X=B

where xor is the bit-wise xor operator and + is the modular addition. For example, A,B and X can belong to the set{0,1,...,255} so the addition is modulo 256.
This equation can be a replacement for classical xor operation used by stream ciphers. If this equation cannot deterministically be solved then a known plain-text attack cannot be mounted against the cipher to deduce the keystream....


texts: What is the importance of $f_k$ in a feistel network being a permutation

texts: I was doing some cryptography exercises, one of which was an example of a feistel network. It said that the function $f_k$ was a permutation for all k but didn't explain why that makes a difference. So what is the importance of a function being a permutation in a feistel network?


texts: Layman's description of the padding oracle attack

texts:
I understand that the MAC-then-encrypt approach is susceptible to several attacks including the so called padding oracle attack. I understand that in this attack the attacker modifies the padding and listens for the errors caused which he can then use to infer the plain text. Can someone please explain the attack in layman's terms?

I would like to have the following addressed in the answers:

How does the attacker listen for these errors? Does it mean the attacker is assumed to have some malware installed on the host machine doing the decryption?
Is the attack based on a cipher text captured by the attacker, or a chosen cipher text selected by the attacker?


texts: Can we use a Merkle Tree structure to reduce digest size?

texts:
A 2nd preimage attack is possible on the standard Merkle tree as pictured below.

I'm aware that we can add identifiers (to differentiate nodes) to the input of each hash as discussed in the link.  If then using a good hash function, it should be resistant to any kind of attacks.
However it would be preferable to have a tree structure where a change in L1 (even if it hashed to Hash0-0) would affect Hash0.
If such a tree structure is viable, it seems we could use it to reduce the digest size used, without necessarily reducing security to the same degree.
That is, if it is difficult to find a pre-image collision in a secure 256 bit digest with a 256 bit input, is it just as difficult to find a pre-image collision in a 128 bit digest when the 256 bit input is constrained by being used further up the tree?
To use a rubbish hash as an example.  For MD5, it may be possible to find a pre-image collision for X.  Is it harder if I ask you to find an input that hashes to X, where the input must also be used to create another pre-image collision at the parent/grandparent of X?
To illustrate my idea, see a simple example of what I imagine below.  Everything except the red blocks would be 128 bit.  'Split & XOR' is splitting the 256 bit DATA block into two 128bit blocks and XORing them together.

The aim being that the attacker (after seeing DATA0 and relevant auth path) cannot simply provide an alternative DATA1, as it will also need to 'Split & XOR' to create the correct parent block. The idea is the attacker is left to find the real 256 bits of DATA1, not just a pre-image for the 128 bits of HASH1.
Questions

Is this a viable idea?
Is such an idea (obviously not as rudimentary as mines) employed anywhere?


texts: Layered encryption in mixnets with post-quantum cryptography

texts:
I am trying to implement a mixnet using post-quantum public-key crypto. Each message may be encrypted by up to 10 levels of public keys, shuffled, before the layers of encryption are stripped off one by one.

This is traditionally achievable in RSA, because the ciphertext is barely larger than the plaintext, but in the many popular post-quantum public key cryptosystems (based on lattice crypto), such as NTRU, it appears the ciphertext becomes an order of magnitude larger than the plaintext. So encapsulating a message in multiple layers of encryption is infeasible as the ciphertext doesn't scale.

Are there post-quantum public key exchange schemes suitable for this purpose? I've looked at the Open quantum safe project, but am unsure whether any of protocols there mitigate this issue, or are mature enough.


texts:
Let $G$ be a group of prime order $p$ and generator $g$.
Let $msk_i = (x_i, y_i) \in Z_p^2$ be two master secret keys and $mpk_i = (g^{x_i}, g^{y_i})$ the corresponding master public keys, $i \in [0, 1]$.
Let $dpk = g^{x_i} \cdot g^{H(y_i)} \in Z_p, i \in [0, 1]$ and $H$ is a hash function, be a derived public key from one of the master public keys.
We want to know if $dpk$ is derived from the first or the second master public key, i.e., if $i=0$ or $i=1$. This problem is equivalent to the discrete logarithm problem, right? How can I make the reduction?


texts:
I am trying to figure out why it is necessary S-box's to be nonlinear. I have been searching for some materials but was not able to find out clear proof why it means that if we use S-box in DES, it would also be linear. I was watching Coursera's course for Cryptography. I didn't understand where this matrix $B$ comes from. We want to map 64 bits to 64 bits.

But why should we use $[m, k_1, k_2,\ldots,k_{16}]$ column?
How do we build $B$ matrix?


texts: What does the "description of group $G$" includes?

texts:
I was reading here:second discrete log meaning in the solution and also here:key generation, first point where the say given $G$ (or its description). My question is what does this description includes?

For example here he is making the differentiation that in Elliptic Curves this group description makes it harder to solve the discrete log problem.
Is it because for example in RSA the group elements are known beforeh and so their group description is just all numbers mod n while in the EC the group elements are not known and you are only given the EC parameters (i am not sure about the last one)?


texts: How to use Montgomery arithmetic for elliptic curves (FIAT cryptography)

texts:
Let us consider the source code for curve P-256 from BoringSSL. This source code can be found here. This source code uses the FIAT generated implementation for field arithmetic. This implementation can be found here. In the source generated by FIAT can be found functions for doing multiplications and additions modulo a prime (the prime from curve P-256). These functions operate on numbers in the Montgomery domain. In the p256_32.h, the function fiat_p256_from_montgomery translates a field element out of the Montgomery domain. The problem is that there is no function that translates a field element into Montgomery domain.

For example, I want to implement point doubling on curve P-256. The inputs will be a 32-byte number that represents x-coordinate and a 32-byte number that represent y-coordinate. If I want for example to square the x-coordinate I cannot use the function fiat_p256_square (provided by the FIAT generated source) because my 32-byte number isn't in the Montogomery domain. I could implement a function that translates a field element into the Montgomery domain but I find it odd that such a function is not already implemented (since this appears a critical function).

Can anybody explain to me what's the catch here? Do I really have to implement a function that translates a field element into the Montgomery domain or did I miss something?


texts: Difference between collision resistance and target collision resistance

texts:
For a hash function, what's the difference between Collision Resistance and Target Collision Resistance?.

I understand the definition of hash function collision resistance, but I don't know about Target Collision Resistance.


texts: Does key authentication in SSH protect from MitM?

texts:
How do cryptography in SSH(2) work (secure channel establishment, authentication)?

Does key authentication in SSH(2) protect from MitM by providing authentication and integrity and why?


texts:
I have a power trace of a decryption.
It seems like I'm watching a 18 rounds decryption algorithm.
I cannot think about any other algorithm implemented in ASIC except Cammelia who has 18 rounds.

Which other algorithms are commonly used in ASIC and has 18 rounds ?

Also it seems it receive 128 bits block size.


texts:
While reading the Wiki page on RC4 I noticed that the key size must be in the range of 40–2,048 bits. So should I understand like this, that I can have a key that has length of, lets say 333 bits? (any decimal number between 40-2048?) How about inputs length?

Imagine that I can ask a user to give me an input length (for example, 1027) and keylength (lets say, 359) and I can use them?

Same question about RC2 - the key size must be in the range of 8-128 [bits] and RC5 - the key size must be in the range 0 - 2040 [bits].

Can I use any key length which is in the given range? Even the exotic one, like, I dont know, 879 or 123 bits as the length of the key?


texts: Digital Signatures, Standard Hash Functions and MACs

texts:
I'm studying Hash functions and Digital Signatures in sequence, and came up with some doubts about their usage.

First of all:

What is the difference between hashing a document and signing it?
And why aren't Standard Hash Functions considered fit for message authentication?

More specifically, considering Keyed Hash functions (MACs):

Are keyed hash functions (MACs) the mechanism on which Digital Signatures are based, or are they a way to implement a particular scheme of Digital Signature (e.g HMAC provided along with the message)?


texts: Signal protocol, how is Signed PreKey created?

texts:
I am getting confused with what exactly is the nature of the Signed Prekey (SPK) used in signal protocol.
I understand what it is used for, but I think the confusion stems from its name.
Is it just the normal key-pair whose public part will get signed and sent to the server as a part of the "key bundle"?

Which means, THAT exact SPK that we send in the bundle as well is just a random public key, and is in no way signed or modified by the IdentityKey itself.

To conclude:

Based on my understanding, this SPK could also be named "Key that WILL get signed but IS NOT signed"
Or is there a previous key, lets call it just "PreKey" that gets signed by IdentityKey and thats how we get Signed PreKey?

I sound like a crazy person to myself and it's really hard to even formulate this question. I've read technical paper on signal's website and also whitepapers of signal implementation in WhatsApp but still I'm getting confused how is this SPK obtained?

Hope this doesn't look like non-sense.
Thanks


texts: Counter Mode: how to choose the nonce part of the counter?

texts:
Suppose:

The "counter field" is about: NONCE || CTR-VALUE.
I have multiples messages $M_a, M_b, M_c, \dots$
Each message can be divided into x-bits blocks ($M_{a1}, M_{a2}, M_{a3}, \dots$).

Each message $M$ (for instance $M_a$) is encrypted following a randomly and uniquely generated key. In this case, does I really need the NONCE part of the "counter field" ?
If I really need a nonce, and knowing that each key is again unique-per-message, is there a secure way to derivate the nonce from the key ?


texts: Key Derivation Functions vs. Password Hashing Schemes

texts:
Key derivation functions, such as HKDF (standardized in RFC 5869), are meant to stretch some initial keying material having enough entropy, like a Diffie-Hellman shared value, into one or more strong cryptographic secret keys.

Password-hashing schemes, such as the PHC winner Argon2, are meant to hash usually low-entropy passwords with the goal of making the hash digest inversion as costly as possible for an adversary with respect to CPU and memory consumption, as well as parallelization.

Is it exact to consider that password-hashing schemes are actually key derivation functions specialized for low-entropy inputs? Or is there any other essential difference of theoretical nature between these two types of cryptographic schemes?


texts: How to prove that weak one way functions cannot have polynomial-sized ranges?

texts: I figured how to show that strong OWFs cannot have polynomial sized ranges. But I am unable to prove the same for weak OWFs.


texts: Is there an encryption algorithm with a key that can only be used to decrypt?

texts: I was wondering if there were any encryption algorithms that kinda worked like RSA in the sense that there are two keys, however, one of the keys only decrypts (meaning you can't encrypt with it) and the other key that only encrypts. Is this possible?


texts:
libsodium verifies that the HMAC is correct with the following code:

return crypto_verify_32(h, correct) | (-(h == correct)) | sodium_memcmp(correct, h, 32);

where crypto_verify_32 is

for (i = 0; i < n; i++) {
    d |= x[i] ^ y[i];
}
return (1 & ((d - 1) >> 8)) - 1;

and sodium_memcmp is

for (i = 0U; i < len; i++) {
    d |= b1[i] ^ b2[i];
}
return (1 & ((d - 1) >> 8)) - 1;

Why not using a simple memcmp?


texts: Is it possible to create a zero-knowledge proof that a number is more than zero, and less than x?

texts:
Note: This might be similar to this question.

I'm thinking about a hypothetical cryptocurrency where the blockchain doesn't store any transactions. The balance of an address would be stored by the owner, and the blockchain would only contain the root hashes for Merkle trees with hashes of "{address}{balance}". Each block would also contain a list of invalidated hashes. The "miner" nodes would execute a transaction by invalidating the previous hash for an address, send both parties the new Merkle tree leaf nodes for the updated balances, and create a new block with the root hash. It would also be a proof-of-stake algorithm.

I would like to know if there's some way to generate a zero-knowledge proof that your address contains more than 0, and at least x? (x can be an integer, since this hypothetical cryptocurrency has a fixed number of decimal places.)

This would allow people to send transactions without disclosing their actual balance. They could also provide a sequence of verified transactions to prove that their address contains the original amount, minus x, y, z, etc.

I've read some of the other zero-knowledge answers on here, so I'm pretty sure that the answer is "yes". I found this paper, and I've also found some answers like this. However, I would love to see an answer that is relevant to this specific case. I would also find it easier to understand some code examples (any language, or even pseudocode.)

EDIT: I forgot to mention something: the implementation must also include a nonce, otherwise it would be very easy to bruteforce balances for some addresses. For example, if there was no nonce, then it would be easy to find a list of all addresses that have a specific balance of 1.00000000. So the range proof / verification must also consider a secret nonce (or salt).


texts: The goal, the method, and the interface of the signcrypt primitive.

texts:
Some time ago, I proposed making the site more educational by teaching correct cryptographic programming. The proposal had had somewhat good reception, but was met with cold ice as there had been little new questions on this topic.

Therefore today I'd like to ask a question centralize the idea behind the correct programmatic usage of the signcrypt (Sign and Encrypt) primitive.

The goal of signcrypt in its simple form can be stated as: to ensure the confidentiality of a non-repudiatable, authentic, integral message for its intended recipiant (correct me if I've mis-stated it). From this, I have the following questions at hand:

Per this recent question, should we a) query the signing oracle on the encrypted message, or b) query the encryption oracle on the signed message?
What is the interface of signcryption? What functions does the tuple consist of?
As it deserves a topic of its own, in short summary how does signcryption fit into the big picture of instant messaging protocol like the Double Ratchet Algorithm?


texts: How to prevent cache timing attack on table lookup AES implementation?

texts:
I've been trying to find a solid method to prevent cache timing or other possible side channel attacks on an AES implementation, that uses lookup tables for S-box substitution.
I realize that there are methods to eliminate table lookups using techniques like BitSlice AES and also AES NI instruction set. But I'm stuck with a self made implementation that depends on 256 byte S-box lookups. An attacker observing a shared CPU cache can easily observe my patterns of access and hence gain information about the secret keys used.

I've tried various techniques to make table lookup undetectable, but it all seems to have some vulnerabilities, and some of them are performance taxing.

Can I apply any programming hacks on the table or its storage or ways to access it to make cache timing attacks difficult for an attacker, but not loosing performance?

So, are there methods to prevent an attacker from knowing a table lookup, and make it difficult for an attacker as brute forcing AES ?

Also, how difficult is a practical cache timing attacks/side channel attacks on AES that uses 256 bit keys?

Is AES-128 more vulnerable to side channel attacks than AES 192 or AES 256 ?

Every help and advice will be greatly, appreciated!


texts: Size of Key Material of TLS_DHE_RSA_WITH_AES_256_CBC_SHA

texts:
What is the size of key material required for generating MAC keys, encryption keys and IV when use TLS_DHE_RSA_WITH_AES_256_CBC_SHA ?
How to calculate it?


texts:
Given the equation
$$m^3 = k\cdot n + c$$
I know $n$ and $c$, and I need to find $k$, so that $m$ is a natural number. $n$ and $c$ are large numbers, so i can't use bruteforce.

How can you find a solution?


texts: Could the Enigma algorithm be classified as a Feistel network?

texts:
The Enigma algorithm is a encryption method that was developed (I believe) by the Germans in WWII. It went a little something like this:

When a letter was typed on the keyboard of the Enigma machine, it was first sent through the first rotor, which would shift the letter according to its present setting. The new letter would then pass through the second rotor, where it would be replaced by a substitution according to the present setting of the second rotor. This new letter would in turn pass through the third rotor, again being substituted accordingly. Next, this new letter would be bounced off of a reflector, and back through the three rotors in reverse order. The trick that made Enigma so powerful for its time though, was the spinning of the rotors. As the plain text letter passed through the first rotor, the first rotor would rotate one position. The other two rotors would remain stationary until the first rotor had rotated 26 times (the number of letters in the alphabet and therefore, one full rotation). Then the second rotor would rotate one position. After the second rotor had rotated 26 times (26X26 letters, since the first rotor has to rotate 26 times for every time the second rotor rotates), the third rotor would rotate one position. The cycle would continue like this for the entire length of the message. The result was a shifting shift. In other words, an s could be encoded as a b in the first part of the message, and then as an m later in the message. This principle of the shifting rotors allowed for 26X26X26 = 17576 possible positions of the rotors.
In order for the recipient to decode the message, they would need to know the initial settings of the rotors, and then put the cipher text through the machine to find the plain text. The Germans devised a system by which all of the recipients would set their rotors to predetermined settings according to the date. Each clerk had a book detailing the settings for each day.

Although (I believe) a true Feistel involves splitting into two halves (which doesn't happen here) and where one old half == other new half after a round of encryption, could this algorithm be classified as a Feistel network?


texts: AES-256 with random key generation instead of hash

texts:
In order to use AES256 encryption, we will need a 256 bit key, and 128 bit iv. We will need some kind of salt and hashing function to convert a password to the desired key.

However, let's assume the password is automatically generated for every file anyway. This means that we can theoretically skip the salt and hash (e.g. pbkdf2), and just generate a random 256 bit key and 128 bit iv. Is there any security implication which might be generated from this?


texts: What happened to Poly1305AES? Is it obsolete?

texts:
I've been told that Poly1305AES is a great choice of MAC for constrained (embedded) environments. I'd checked out DJB's writing on it briefly, and have to say that I found its simplicity likeable, performance convincing & security proofs rigorous enough.

But also, libsodium author has told me today that his library won't support this construction.
Because... "it's not used anywhere". I'm baffled by this scarce an explanation.

I'm also confused, since libsodium does support XChaCha20-Poly1305, and AES sure thing — so it has all the primitive pieces; but won't give the combined construction.

Frank Denis also said:

  There is nothing wrong with [poly1305aes], but it's not used anywhere, and it wouldn't have any benefits over existing constructions.

What are those existing constructions? Do I guess correctly, HMAC-SHA2?..

Please shed some light onto the algo; I'm pretty far from advanced cryptography, and this interaction (+ my followup research) only makes me feel "I know that I don't know much".


texts: How to judge a determinant equals non-zero in cryptography?

texts:
In the paper [1,p5], the authors construct a matrix to find out $n$ solutions of a equation set as follows:

where $c_i$ is generated by the adversary, $c$ is picked by the simulator. Note that $c^i$ means different forgeries instead of exponent.

My question is, they find out $n$ solutions iff the determinant equals non-zero, but they don't prove why the determinant equals non-zero. There is no need to prove it?

(I'm not true this is a crypto problem or not, it seems more like a math problem?)

[1] Liu, J. K., Au, M. H., Susilo, W., & Zhou, J. (2014). Linkable ring signature with unconditional anonymity. IEEE Transactions on Knowledge and Data Engineering, 26(1), 157–165. https://doi.org/10.1109/TKDE.2013.17


texts: Are there any differences in operation between existing Diffie-Hellman specifications?

texts: Are there any differences in operation between existing Diffie-Hellman specifications, especially those within the RSA PKCS#3, ANSI X9.42 and RFC 2631 standards?


texts: How can I compute the theoretical total key-space for 521 bit elliptic curve ECDH private keys?

texts:
Assume a dumbed down RSA: the private hey is $3 \times 5 = 15$. $3$ and $5$ are the private key and $15$ is the public key. To brute force it, find the two prime factors of $15$ ($3$ and $5$).

Is there a way to demonstrate a "dumbed down" elliptic curve / discrete log problem that I can compute by hand? I get the feeling that it has to do with integer points on a complex curve so how do I know the value of n assuming that refers to the number of integers in the set {1,..,n-1}?

Or to put another way - is there a smallest key size I can investigate to learn about brute forcing this formula. Performing countless log functions does sound quite CPU intensive.

Simple Curve Example

According to https://en.wikipedia.org/wiki/Elliptic_curve the region [−3,3] is a very simple curve where you get a nice "coat-hanger" with values of a=-2 and b=2

Considering that:

  "the private key is a random integer $d$ chosen from $\{1, \dots, n -
> 1\}$ (where $n$ is the order of the subgroup)."... and also: "The
  Diffie-Hellman problem for elliptic curves is assumed to be a "hard"
  problem. It is believed to be as "hard" as the discrete logarithm
  problem, although no mathematical proofs are available. What we can
  tell for sure is that it can't be "harder", because solving the
  logarithm problem is a way of solving the Diffie-Hellman problem."
  Source: https://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/

Or to put it another way, how can I prove this, or where did these numbers come from:

  Another way is with RSA, which revolves around prime numbers. Most
  cryptocurrencies — Bitcoin and Ethereum included — use elliptic
  curves, because a 256-bit elliptic curve private key is just as secure
  as a 3072-bit RSA private key. Smaller keys are easier to manage and
  work with.Apr 7, 2018

Or... perhaps n not knowable for curves like Curve25519 for example?


texts: Necessary to authenticate nonce if authentication-key is derived from nonce?

texts:
Lets suppose my messages are composed like this: unique_message_nonce + encrypted_message + mac

Because I don't have an AEAD-scheme, I can encrypt and authenticate my message in two ways:

Use authenticated-encryption for message:

let key = KDF(key: master_key, info: "Key:" + unique_message_nonce)
let nonce = KDF(key: master_key, info: "Nonce:" + unique_message_nonce)
let (encrypted_message, mac) = AuthEnc(key: key, nonce: nonce, message: message)

Encrypt the message and compute MAC over unique_file_nonce + encrypted_message:

let encryption_key = KDF(key: master_key, info: "EncKey:" + unique_message_nonce)
let encryption_nonce = KDF(key: master_key, info: "EncNonce:" + unique_message_nonce)
let encrypted_message = Enc(key: encryption_key, nonce: encryption_nonce, message: message)

let mac_key = KDF(key: master_key, info: "MACKey:" + unique_message_nonce)
let mac = Auth(key: mac_key, message: unique_file_nonce + encrypted_message)

Is the first one secure?

Usually, you would use the 2nd one and authenticate everything because if s.o. tempers with the nonce, he might be able to alter the plaintext without changing the MAC.

However, as far as I can see, in the 1st one the unique_message_nonce is implicitly included in the MAC:

If s.o. changes unique_message_nonce, key will change too and the authentication will fail
Without knowing master_key, an attacker cannot manipulate unique_message_nonce to create a malicious key


texts: Where is the "Letter to NBS, October 22, 1975"

texts:
Discussions of the weakness of the U.S. Data Encryption Standard frequently cite a letter by Martin Hellman and Whitfield Diffie to the National Bureau of Standards that reported stated:

Whit Diffie and I have become concerned that the proposed data encryption standard, while probably secure against commercial assault, may be extremely vulnerable to attack by an intelligence organization" (letter to NBS, October 22, 1975).

I've been trying to find a scan of the original letter, but all I can find is the above quotation, which seems to have been faithfully repeated in many publications (for example, here).
Interestingly, this book attributes the letter solely to Martin Hellman.
Where can I find the original letter?


texts: Is it possible to match encrypted documents using user-defined search terms?

texts:
Suppose I am storing a number of encrypted documents in a database. I would like to make it possible to identify the subset of documents whose contents match user-specified search terms without a) maintaining a plaintext index or b) decrypting documents on the fly. Is there any way to accomplish this securely?

By the same token, I'm wondering if a collection of encrypted documents can be sorted according to an encrypted attribute (e.g., document title) without first decrypting all attribute values.


texts: Why do "nothing up my sleeve numbers" have low entropy?

texts:
As a preface, forgive me for some of the links being from Wikipedia.  I realize that academia frowns upon this.

I came across this article about "nothing up my sleeve numbers".  In it, it says:

  In cryptography, nothing up my sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties.  [...]  Such numbers can be viewed as the opposite extreme of Chaitin–Kolmogorov random numbers in that they appear random but have very low information entropy.

In looking for an example of one of these numbers, I came across this Crypto Beta Q&A, where the answerer says:

  [M]athematical constants like binary expansions of irrational numbers like 2√ (or roots of other numbers), e, π can be used, to show that one didn't select the numbers to create a back door.

This is what Wikipedia has to say about information entropy:

  Entropy is typically measured in bits, nats, or bans.  Shannon entropy is the average unpredictability in a random variable, which is equivalent to its information content. Shannon entropy provides an absolute limit on the best possible lossless encoding or compression of any communication, assuming that the communication may be represented as a sequence of independent and identically distributed random variables.

Based on this, I don't see why these numbers (or any possible number) can have low entropy.  It seems like all numbers have equal likelihood of being generated as a "random variable" as long as that number is within the generated range (e.g., if the number is 1564631 [assumed to be one of these kinds of numbers], and I'm looking for number between 1 and 2000000, it has an equal likelihood of being generated, regardless).

Can anyone explain this concept?  I looked at the definition of entropy, but I admit that the math is a little over my head.  I'm not sure how someone would use a number without these properties to "create a backdoor."


texts: Storing values under different keys (e.g. during key rotation)

texts:
If you are encrypting some secrets (database passwords, access tokens, etc).

When it comes to key rotation, you'll need to store those encrypted values twice, for a short period of time (under the old and new keys).

Could the encrypted secrets be stored in two files named after the hash of their keys? maybe sha256?

Or could those file names (if known) be used in a malicious way? perhaps making it easier to determine the key values?

An alternative would be to use the keys to encrypt a known plain-text value, and use that for the file names.

I'm currently considering using libsodium, and "IETF ChaCha20-Poly1305" (aead_chacha20poly1305_ietf), to encrypt the secrets.

Why I'm not using 'secrets.new' and 'secrets.old'...

This will be used for some websites, where the script running will simply be given a key to decrypt the secrets (via an environment variable), I'd like to avoid having to also say if it's the new or old key.

Secondly, lets assume the website also has this security vulnerability:

<?php

    $path = '/path/to/file/' . $_GET['file'];

    readfile($path);

?>

It might not be that obvious, but the attacker won't know what the file will be called if it's based on the key (you see a similar thing with the Firefox profile directory).

As a very rough implementation:

<?php

//--------------------------------------------------
// Functions

    function secrets_set($key, $secrets) {

        $nonce = random_bytes(SODIUM_CRYPTO_AEAD_CHACHA20POLY1305_IETF_NPUBBYTES);

        $encrypted = sodium_crypto_aead_chacha20poly1305_ietf_encrypt(
                json_encode($secrets),
                $nonce,
                $nonce,
                $key
            );

        $name = hash('sha256', $key);

        $path = SECRETS_FOLDER . '/' . $name . '-' . bin2hex($nonce);

        file_put_contents($path, $encrypted);

    }

    function secrets_get($key) {

        $name = hash('sha256', $key);

        $prefix = SECRETS_FOLDER . '/' . $name . '-';
        $path = NULL;
        $nonce = NULL;
        $secrets = NULL;

        foreach (glob($prefix . '*') as $match) {
            if (($pos = strrpos($match, '-')) !== false) {
                $path = $match;
                $nonce = hex2bin(substr($match, ($pos + 1)));
            }
        }

        if ($path) {

            $secrets = file_get_contents($path);

            $secrets = sodium_crypto_aead_chacha20poly1305_ietf_decrypt(
                        $secrets,
                        $nonce,
                        $nonce,
                        $key
                    );

            $secrets = json_decode($secrets, true);

        }

        return $secrets;

    }

//--------------------------------------------------
// Store

    $key1 = sodium_crypto_aead_chacha20poly1305_ietf_keygen();

    secrets_set($key1, [
            'database' => 'u8syTtAvNWJbhwMNdFdRsfxJY',
            'api_key1' => 'y9f82wZdkahEPsyjXQAmy6nPh',
            'api_key2' => 'YtMp4pHR9EbHbGJXgRiniQixU',
        ]);

//--------------------------------------------------
// Get

    print_r(secrets_get($key1));

//--------------------------------------------------
// Re-key

    $key2 = sodium_crypto_aead_chacha20poly1305_ietf_keygen();

    secrets_set($key2, secrets_get($key1));

    print_r(secrets_get($key1));
    print_r(secrets_get($key2));

    // When $key1 is no longer in use, delete the old file.

?>


texts:
I am working on a project where I am benchmarking the 5 AES finalists (Rijndael, Twofish, Serpent, MARS and RC6) on CUDA Hardware.

My problem is that I am no experienced CUDA programmer. My approach is to find open source projects that implement these algorithms in CUDA and modify them to match my needs.

It was obviously no big problem to find Rijndael implementations. Twofish and Serpent were also no big problem. But I can't find anything about MARS and RC6. I already heard that with these two algorithms there might be some problems with royalty but I am not sure how serious this is.

Anyway, does anybody know if there is some source where I can find CUDA implementations of these algorithms? If there isn't something I would have to write them myself but I think these won't be good for Benchmarking.


texts: Question about TLS v1.2 Ciphers on my Web Server

texts:
I need some help to understand the Ciphers being used by my web server running TLS v1.2.

What I understand is that my web server is configured to use only the listed methods of encryption. I suspect that it is telling the clients that it uses TLs v1.2, but my questions are:

How is DHE, ECDHE being used with RSA?
How is CBC, GCM being used with SHA?
Which one is the better one to use?
Should I used ECDSA instead of ECDHE?

ciphers:
|       TLS_DHE_RSA_WITH_AES_128_CBC_SHA (dh 1024) - A
|       TLS_DHE_RSA_WITH_AES_128_CBC_SHA256 (dh 1024) - A
|       TLS_DHE_RSA_WITH_AES_128_GCM_SHA256 (dh 1024) - A
|       TLS_DHE_RSA_WITH_AES_256_CBC_SHA (dh 1024) - A
|       TLS_DHE_RSA_WITH_AES_256_CBC_SHA256 (dh 1024) - A
|       TLS_DHE_RSA_WITH_AES_256_GCM_SHA384 (dh 1024) - A
|       TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA (secp256r1) - A
|       TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256 (secp256r1) - A
|       TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (secp256r1) - A
|       TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA (secp256r1) - A
|       TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384 (secp256r1) - A
|       TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (secp256r1) - A
|       TLS_RSA_WITH_AES_128_CBC_SHA (rsa 2048) - A
|       TLS_RSA_WITH_AES_128_CBC_SHA256 (rsa 2048) - A
|       TLS_RSA_WITH_AES_128_GCM_SHA256 (rsa 2048) - A
|       TLS_RSA_WITH_AES_256_CBC_SHA (rsa 2048) - A
|       TLS_RSA_WITH_AES_256_CBC_SHA256 (rsa 2048) - A
|       TLS_RSA_WITH_AES_256_GCM_SHA384 (rsa 2048) - A


texts: Why not use CBC, not send IV, and assume first plaintext block is garbage?

texts:
Possible Duplicate:
  Using CBC with fixed IV

Forgive me if this has been asked before, I looked but haven't seen any answers that suit.

Is there any danger in using CBC, encrypting a message plus one initial block of garbage, discarding the IV, and when decrypting, use any random IV, and then discard the resulting initial plaintext block?

I'm sure I'm not the only one to confront this question.


texts: Why Sflash signature scheme is constructed in this way?

texts: Sflash is a Multivariate signature scheme that was accepted by NESSIE in 2003, and completely broken in 2007 by a differential attack. Despite I know the total break of Sflash signature scheme and the fact that it's highly insecure to be used, I'm trying to understand an interesting technique used in this signature. My question is why in this signature, The 80bit secret $\Delta$ is concatenated to V=SHA-1(M,...) and then the first 77-bits of SHA-1(V||$\Delta$) is computed? What's wrong with a completely random 77-bit string instead of SHA-1(V||$\Delta$)? What's the advantage of using a random string which relates to the plain message M as well?


texts: Are there any mutual-distance bounding protocols in RFID context?

texts:
Distance-bounding algorithms are a classical solution for the Relay Attack, wherein a verifier can determine an upper bound on its distance from the prover.
However, recent literature is discussing the concept of mutual distance-bounding, where both sides of a transaction can measure this upper bound, to overcome the risk of a compromised or even malicious verifier.
However, all these algorithms and proposed protocols, despite being theoretically promising, don't address how a mutual DB protocol, would be implemented in an RFID context; that is a passive RFID tag is one side of the transaction. How can this be done? How can we implement a time-keeping mechanisms on a passive RFID tag to have it approximate or restrict the distance to the verifier?


texts: Advantages of RSA / EC against QC attacks

texts:
We know that both the RSA and ECC algorithms are vulnerable against attacks using (future) Quantum Computing (QC). Are there however any advantages of choosing one algorithm over the other?

As an example: would it be possible that the larger key size of RSA has advantages over the short key size used by ECC, possibly with regards to the amount of qbits or qbit configuration required? Would such an advantage matter in practice?


texts: The exact definition of a symmetric encryption

texts:
I have doubts for the definition of the decryption algorithm $D(.)$. I think I've already seen that the decryption returns a plaintext $M$ on input the key $K$ and $C=E_K(M)$.
I have also seen that the decryption algorithm returns either $M$ or the special symbol $\bot$.

Is the first definition valid in the case of symmetric encryption? Especially when we deal with non authenticated encryption...


texts: Why do we keep designing new static s boxes?

texts:
As I understand s box properties, they primarily need high non linearity and low auto correlation.  But most importantly for this question, they're not secret.

There are many questions on this site asking for help in generating them.  And new ciphers always seem to have new s boxes.  Why?  There are proven numerical optimisation techniques such as tree search and hill climbing to optimise a function.  Could we not just devote an hour of a large computer cluster to generate optimum (say) 3, 4, 5, 6, 7 and 8 bit wide s boxes?  Universities have access to such resources.  They could then be published in a book rather like they used to publish random numbers.

Note: By static s box, I mean one of those that isn't related to a key like Blowfish's.


texts: How to construct a good PRF from a block cipher?

texts:
We want to explicitly construct a good (as tentatively defined below) Pseudo-Random Function $F$ with $b$-bit input and output, from (preferably just) one Pseudo-Random Permutation $E$ of $b$-bit, as instantiated in practice by TDEA for $b=64$ or AES-256 for $b=128$, and one fixed random secret key.

I tentatively define a good PRF to be one indistinguishable (with small constant advantage) from a random function, assuming $2^{b(1-\epsilon)}$ queries to an oracle implementing our construction of $F$ from $E$, and delegating invocations of $E$ (edit: and in addition of $E^{-1}$ if that helps) to a random oracle for that. Fix this definition as necessary (Update: I'm told by the answers that for $\epsilon<1/2$, this is roughly what's called a PRF with beyond the birthday bound security).

Are there simple constructions of $F$ from $E$ with a security argument?

$F(x)=E(x)$ is squarely unfit: it can be distinguished from a random function by detecting collisions after $2^{b/2}$ distinct queries, which happens with sizable probability for a random function but not for a random permutation. That can even be done with constant memory, using Floyd's cycle finding. A distinguisher can also be built against $F(x)=E(x)\oplus x$.

Right now I fail to find a distinguisher for $F(x)=E(E(x)\oplus x)$, but that's not even a weak security argument. Update: If the security of that is unprovable, I'm still interested by a distinguishing attack, in order to get a feeling of how insecure in practice that could be.


texts:
Let's say I have a list of several million numbers, with only 6-9 digits of secret information per number (this means that an attacker might efficiently guess the other digits). I have to store the list in an unreadable format and when given a new number I want to efficiently know if I have the number in my list or not.

For this purpose I store the HMAC – SHA 256 of my numbers, using the same secret key to generate all the hashes. When given a new number I use the secret key to compute its HMAC - SHA 256 and perform a lookup in my list.

I am also storing the same numbers encrypted with another key in AES CBC mode, but this field is not useful for searching because of the random IVs.

Is this secure, cryptographically speaking? Will it prevent attacks to "open" the hashes, assuming the secret key remains unknown to an attacker?


texts: Algorithm for computing modular inverse in MPC

texts:
Is there any known algorithm for calculating $a^{-1} \pmod{q}$, where $ q < p$ and $F_{p}$ is the prime field of the MPC, in a linear secret sharing scheme ?

I have tried using the standard algorithm, in which the parties generate $r$, then run secure multiplication on shared values to get $r⋅a$ and open it, and then each local invert the result. Finally, each uses local scalar multiplication of their share of $r$ to get shares of $a^{-1} \pmod{q}$.
However this doesn't work when the field of inverse is different from the MPC field.


texts:
I have a question regarding the relationship between the (search) LPN problem and the GapSVP problem.

I have read a related problem that explains the main theorem in Reg05: the GapSVP problem can be reduced to a search LWE problem (especially, the modulus $p>2\sqrt{n}$).

  What is the direct connection between LWE and GapSVP?

However, regarding the hardness of the search LPN problem, I noticed that some papers just introduce that the known fastest algorithm that solves the search LPN problem needs $2^{O(n/\log n)}$ time (i.e. BKW algorithm).

I was wondering, whether there are some similar mature results about the relation between the search LPN problem and the GapSVP problem? Or, we believe the search LPN problem is hard, SOLELY because there is no known attack in polynomial time?

Many thanks.


texts: How can I store asymmetric keys server-side, so that they are only readable by devices?

texts:
I am building a platform in which there is a central server & devices (computers).

These computers hold the same keys pairs that correspond to specific resources (shared between devices), so that only these devices can return signed data if required.

In that setup my question is:

How to store keys on the server-side, with only devices being able to read them AND no device interactions to replicate those keys?


texts: Do I have to transfer the private key to digitally sign a remote document?

texts:
I'm trying to digitally sign a document which is uploaded by a user. I want the user to sign that document using his digital signing certificate (DSC).

Should I:

transfer the file to the user, and have them sign it on their own system, or
transfer the user's private key to the server, and sign the file there?

Which way is better, or are there any other, better ways to do this?


texts: Some information about zero knowledge proofs

texts: How do I start studying Zero-Knowledge proofs? What are some good books and entry-level research papers on that topic? What are some prerequisites of the same?


texts:
Let $G=\langle g \rangle$ be a cyclic group of prime order $Q$. Let $H_1:\{0,1\}^*\to G$ be a hash function. Is the following a family of PRF for $s \in \mathbb{Z}_Q^*$?

$$f_s(x)=(H_1(x))^s$$

Or equivalently, let $H_2:\{0,1\}^*\to \mathbb{Z}^*_Q$ be a hash function,

$$f_s(x)=(g^{H_2(x)})^s$$

Intuitively it is in ROM, but can somebody prove it?


texts: How can one turn a malleable encryption to not malleable

texts:
An encryption algorithm is "malleable" if it is possible to transform a ciphertext into another ciphertext which decrypts to a related plaintext. That is, given an encryption of a plaintext m, it is possible to generate another ciphertext which decrypts to f(m), for a known function f, without necessarily knowing or learning m.

And non-malleable is the adversary shouldn't be able to come up with a ciphertext whose underlying plaintext is related to the original message through a relation that also takes public keys into account.

My question is how can one turn a malleable encryption scheme into one that is not
malleable?


texts: What is the formula to calculate password entropy?

texts:
I saw in another thread: Is using 7-8 random words from all words of a language as password a good idea?

These calculations:

  If we assume that English has 171,476 words. Then with 8 words the entropy is:

  $$P(171476,8) \approx 7.474 \times 10^{41} \approx 2^{140}$$

  Therefore you will have lower entropy than Bip-39, again. And with 7
  words:

  $$P(171476,7)≈4.358×10^{36}≈2^{122}$$

I like to use this calculation method myself. I have the following related questions:

What is the name of this mathematical formula called $P(x,y)$?
Any online calculator available? Or even better, a formula for MS Excel or python?
Is this method commonly used to calculate entropy? If not please hint me to a more widely used formula.


texts: How was the MDS matrix used in AES chosen?

texts:
$$\begin{pmatrix}2&3&1&1\\
1&2&3&1\\
1&1&2&3\\
3&1&1&2\end{pmatrix}$$
In the above MDS matrix used in AES encryption, why are the numbers $2$,$3$ and $1$ chosen? Why not any other number?


texts: Comparison: complexity measures vs. security

texts:
Assume that you want to compare several cryptographic primitives (say, encryption schemes), and choose one. You need to consider several complexity measures, such as the key length, encryption time, decryption time, etc. In order for the comparison to be fair, all primitives in question must provide the same level of security.

As an example, let us consider RSA, ECC, and NTRU. Assume that we want the cryptosystem to be secure against a passive adversary, whose computational power is limited to at most $2^{100}$ operations. By "passive adversary", we mean that the adversary is limited to chosen-plaintext attacks (since we are comparing public-key encryption schemes). Now, we want to know the key length to be chosen for each scheme.

To answer this question, we consider the complexity of the most efficient attacks against RSA, ECC, and NTRU, which in turn requires a great knowledge of the literature.

  Is there any resource/survey (website, paper, tool, etc.) which helps in such comparisons?

Note: The website keylength.com, while being a helpful tool in its own right, is not an answer to this question. The reason is that keylength.com merely recommends a minimum key length to be used in different scenarios (say symmetric or asymmetric encryption), but leaves out most of the concrete schemes (say, NTRU, twofish, serpent, etc.)


texts: how to calculate the average key search for AES-128bit?

texts:
Assume that an attacker has a special purpose application specific
  integrated circuit (ASIC) which checks $5\times 10^{8}$ keys per second, and she has a budget of $\$1$ million.
  One ASIC costs $\$50$, and we assume $100\%$ overhead for integrating the ASIC (manufacturing the printed circuit boards, power supply, cooling, etc.).

  How many ASICs can we run in parallel with the given budget?
  How long does an average key search take? Relate this time to the age of the Universe, which is about $10^{10}$ years.

I know that we can run $20\ 000$ ASICs with ONE million budget, but I don't understand how to calculate the average key search, is it $2.5 \times 10^{19}$?


texts: Disjunctive zero knowledge proof of equality of committed values

texts:
I have read on ZK proof of equality of committed values, that is for $g^xh^y$ and $g^{x'}h^{y'}$, prove in ZK that $x = x'$ (can also be generalized if generators are different using sigma-protocols).

However I want to do a disjunctive (OR) proof as follows: For $g^{x_1}h^{y_1}$ and $g^{x_{1}'}h^{y_{1}'}$ and $g^{x_2}h^{y_2}$ and $g^{x_{2}'}h^{y_{2}'}$ prove in ZK that either $x_{1} = x_{1}'$ or $x_{2} = x_{2}'$. Any suggestions or ideas?

Upd: As suggested, I should highlight the fact that the generators are the same.


texts: How many bytes of the last keystream block are used to XOR the final block of partial plaintext in CFB, OFB & CTR modes?

texts:
I apologize if this is a dumb question but I'm trying to understand how the final block of partial plaintext is XORed using only n number of bytes in the final keystream block.

How do we determine the number of bytes in the keystream that are required to produce a final block of the same size (128 bit) as the others?


texts: Is secure lattice based cryptography in future?

texts:
Lattice cryptography is a post quantum cryptography that work on two NP-hard problem in below:

Find shortest nonzero vector from origin and
Find minimum distance of a arbitrary point out of lattice from origin.

At the moment lattice cryptography system is broken with key space of dimension 300. On the other hand we use dimension 400 in this cryptosystem. Can we use this cryptosystem in future?

How we can distinguish between this cryptosystem with others?


texts: Difference on montgomery curve equation between EFD and RFC7748

texts:
There is a subtle difference between the 2 implementations for a Montgomery curve defined from the 2 following links

https://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html

      A = X2+Z2
      AA = A^2
      B = X2-Z2
      BB = B^2
      E = AA-BB
      C = X3+Z3
      D = X3-Z3
      DA = D*A
      CB = C*B
      X5 = (DA+CB)^2
      Z5 = X1*(DA-CB)^2
      X4 = AA*BB
      Z4 = E*(BB+a24*E)

https://tools.ietf.org/html/rfc7748

       A = x_2 + z_2
       AA = A^2
       B = x_2 - z_2
       BB = B^2
       E = AA - BB
       C = x_3 + z_3
       D = x_3 - z_3
       DA = D * A
       CB = C * B
       x_3 = (DA + CB)^2
       z_3 = x_1 * (DA - CB)^2
       x_2 = AA * BB
       z_2 = E * (AA + a24 * E)

This AA / BB change on the last line does affect the result of a point multiplication with same input parameters.

Is there a reason for that difference ?


texts: Was the Enigma's double stepping mechanism intentional?

texts: It's sometimes refered to as the double stepping anomaly, so was it just a design flaw or was it put in place deliberately?


texts: Is there a scheme that allows to use RSA based challenge response protocol limited to signing only 8 bytes to create a secure signature of any data?

texts:
I have a tiny device that has a challenge-response authentication mechanism where the device signs 8 bytes of any data with it's internal 2048 bit RSA key.

I would like to be able to certify any data using this mechanism by using a number of challenge-response pairs securely chained together (using only 1 pair already discarded because of insecurity of 64 bit long hashes). Each challenge may contain only 8 bytes, each response is a 256 long SHA256withRSA signature. The requirement is to use as few operations as possible since one operation takes 1 second to execute.

The idea is to securely prove presence of the device in a certain situation.

Any suggestions?


texts: Should I calculate two CMACs over two different strings that share common bytes?

texts:
I am trying to secure my RF communication in which one RF package consists of two separate segments. I need to make sure that one segment of one packet is not replaced with a valid segment of some previous packet, if you know what I mean.

My RF packet is 32 bytes long, and I need to secure it with CMAC (I found an implementation of AES-128 in CBC mode and CMAC - operating on 16 byte blocks). I am planning on doing it like this:

[B1][B2][B3]...[B30][B31][B32] = bytes in my RF packet

[B1] [B2]... [B10] = first segment (10 bytes long)
[B11][B12]...[B20] = second segment (also 10 bytes long)
[B21][B22]...[B32] = remaining bytes of RF packet contain CMAC of first segment,
                     and CMAC of second segment (both truncated to first 6 bytes
                     in order to fit into 32 bytes that I have for one transmission).

Now for the problem: In order to make sure that nobody captures two of my RF packets, and creates third new packet that contain fist segment of packet 1 and second segment of packet 2 (with corresponding CMACs also copied) I am planning on calculating CMAC of first segment + 6 bytes of second segment, and calculating CMAC of second segment by borrowing last 6 bytes of first segment and remaining 10 bytes of second segment.

Should I do this? If not, how can I make sure someone doesn't transmit third custom packet containing two valid segments of my previous transmissions? It would be best if I could somehow calculate CMAC on the entire 20 bytes, but as I know I can only work with 16 byte blocks maximum.


texts:
I know that Elgamal algorithms have fallen out of fashion, and they are not included in any widespread cryptographic standard nowadays. However, they are still present in several popular crypto libraries (bouncy castle, botan, cryptopp, etc). One disturbing thing I found is that such libraries have no or very limited test vectors for Elgamal.

Do test vectors exist at all for Elgamal? What is a good reference? I especially refer to encryption and signing algorithms over $Z_p$.


texts: Choosing asymmetric pairing for Elliptic Curves

texts:
I'm trying to implement a Provable Data Posession protocol using elliptic curves, but am stuck at the $\text{KeyGen}$ phase of choosing a subgroup $G_2$. Here's an excerpt of it.

  On input $\mathcal{K}$, choose an elliptic curve $E(\mathbb{F}_q)$ with a subgroup of large prime order $p$ generated by $P\in E(\mathbb{F}_q)[p]$, such that the bitlength of $p$ is $\mathcal{K}$. Choose an asymmetric pairing $e: E(\mathbb{F}_q)[p] \times G_2 \rightarrow \mathbb{F}_{q^k}^*[p]$ with $G_2$ being a p-order elliptic curve subgroup over (an extension of) the field $\mathbb{F}_q$ with generator $P'$, where the choice of $G_2$ depends on the specific instantiation of the pairing.

If I've understood it right, I can choose some curve, e.g. p256, secp256k1, or something else. But then I also need a subgroup $G_2$.

How do I choose a $G_2$ that satisfies the asymmetric pairing that is stated above?

Link to paper (page 7): https://eprint.iacr.org/2013/392.pdf


texts:
From what I gather from the internet (source), the recommended practice for 2019 and beyond is to avoid RSA and use ECDH and ECDSA.

Is this the general case?


texts:
I have an application where I need to combine a Diffie-Hellman shared secret, with a user's password and derive a key. I'm investigating the possibility of using HKDF to as follows

Initial Keying Material(IKM)= DHE-shared-secret and
salt                        = password-utf-8-bytes

I choose this because the DHE-secret is larger and, has more entropy than the password bytes. Is this correct or should it be the other way around?


texts: Verifying the integrity of ciphertext using the cleartext hash?

texts:
I want to be able to verify the integrity of a ciphertext by providing the cleartext hash, for this to work it would need to:

$$hash(crypt(cleartext)) = f(hash(cleartext))$$

Where $f$ is an arbitrary function mapping the cleartext hash to the ciphertext hash.

Is there such a pair?

Update: I'm trying to prove the integrity to the receiver while delaying the key exchange until I'm ready to commit (send him the decryption details). The hash that proves the integrity comes from another source entirely.


texts: Probability of same input as output in AES 256

texts:
Note: I am assuming that, when entering in the key and plaintext, they are formatted in the same manner as the output of an AES-256 encrypted text.

What is the probability, if any, that you could enter in a key that ends up being the exact same as the output after AES-256 encryption?

and alternatively:

What is the probability, if any, that you could enter in a plaintext (pre-encryption message) that ends up being the exact same as the output after AES-256 encryption?


texts: RSA: Derive modulus from known ciphertexts encoded with same keypairs

texts:
I have two ciphertexts

$c_1 = m_1^e \bmod n$

$c_2 = m_2^e \bmod n$

I know $c_1, c_2, m_1, m_2$ and $e$. Is there a way to derive n from this? I first thought Franklin Reiter but I'd need an $n$ for that which is precisely what I am missing. What other approaches are there?


texts: Good practice to separate RSA key pairs used for encryption and digital signatures

texts:
I've got the following related questions:

If Alice is using the same RSA key pair for both digital signatures and encryption, explain how Bob could forge Alice’s signature on a message of his choice if Alice is ‘foolish’ enough to help him.
What other reasons are there for keeping these key pairs separate?


texts: How can I prove I have a certain Facebook account by signature?

texts: I would like to know how to prove I have certain Facebook account (or that I can login to that account).


texts: RSA: Know the public key from a pair of plain text and their cipher?

texts:
I have two plain texts files cipher with RSA (with the same public and private key) and I have their cipher texts too. Would it be possible know the public key from that information?

My messages have 10 characters and I cannot calculate a huge exponential operation. No padding is used on the messages before encryption.


texts:
We need to choose a mode of operation for a Telnet like application where the average message size is between 7 and 1024 bytes. What is the best mode of operation in this case?

a.  CBC
b.  CFB
c.  CTR
d.  Any of the above is ok


texts: Should I use “modes of operation” for a single block of data?

texts:
I am using AES to encrypt my data. I have only 128 bit block that I am encrypting using AES. I am using AES in CTR (counter) mode, since it is always to advisable to use block ciphers along with modes of operation… but I think this is generally the case when you have more than one block of data.

Should I also be using AES in Counter mode to encrypt a single block?
And does AES of single block in CTR mode enhance my confidentiality?


texts:
I have been going over the CKKS Homomorphic Encryption scheme but I can't seem to understand how the mapping takes place while encoding. I don't get what the line below is trying to convey. I saw this line in a post on Reddit. It would be super great if someone could illustrate this scheme with an example. Thank you!

  The floating point arithmetic operated during the encoding, which maps a N/2 complex array to a N real array, and then rounds to the nearest integer after the scaling of the float numbers resulting from the complex embedding map.


texts: Idiomatic description for an adversary in possesion of a quantum computer?

texts:
I was wondering what the "accepted" way is to describe an adversary who:

is in possession of a quantum computer with which they can efficiently run quantum algorithms such as Grover's or Shor's algorithm.
Is polynomially bounded with regard to solving problems for which no quantum algorithms exist (e.g. finding hash collisions).

I was thinking of something like: quantum capable polynomial time bounded adversary. But I'm not sure whether being able to run quantum algorithms while being polynomial bounded is some kind of paradox?


texts: Which values to store in rainbow table generation?

texts:
According to the Wikipedia and Philippe Oechslin's Making a Faster Cryptanalytic Time-Memory Trade-Off (pdf), both starting points and endpoints are keys. Here is an example from Wikipedia:

As you can see, key kiebgt is the endpoint of this chain.

However, according to this site, it is hash values, rather than keys, that are stored in a rainbow table. That is to say, in the example above, hash value 920ECF10 should be shored as an endpoint.

So which one is the correct approach? The second one seems better to me, because we can skip one calculation(the first step) of reduction function R when looking up.


texts: How can I quickly generate thousands of letters randomly, and strongly mitigate the risk of any compromise?

texts:
I want to generate English letters in a truly random manner without resorting to hand-thrown dice, despite their advantages. Rolling dice would be too slow and tiring as I need four thousand letters.

Using commercially available TRNG software is unacceptable. Depending on a computer to generate the letters by itself, without my oversight is absolutely out of the question.  But I still want to use a computer, albeit an air-gapped computer, because of increased speed and ease, that will carry out and/or record a process of random number generation using some sort of attached equipment (via USB) and/or sensor.

I feel confident about the air-gapped device I built.  The real estate on that device is probably clean.  For software, it's basic: TAILS. If either hardware or software are bad, this will not matter (or will it?) because I am going to control all parameters and watch the process of random number generation at work moment-by-moment.  I do not want a process that merely spits out a complete file that I must trust. Not too slow, not too fast, just right. I want to supervise the process from start to finish.

What simple, cheap equipment and/or software can I and Joe Schmoe use, as outlined above, to generate high-quality random numbers in a way that is faster and easier than throwing dice while still strongly mitigating the risk of compromise, especially against a highly engaged, agile attacker who operates in both passive and active modes?

What process, mechanical or otherwise, can I use on an undorked computer that I control, employing such simple, cheap equipment, that will enable me to generate letters in a truly random manner--most importantly, that yields values which are cryptographically sound--for a proper one-time pad?


texts: Transparent, publicly updatable accumulator with constant-sized witnesses

texts:
I am looking for an accumulator with the following properties:

Transparent: No trusted setup (rules out RSA and pairing-based accumulators)
Publicly updatable: No central authority (rules out digital signatures)
Constant-sized witnesses: (rules out Merkle accumulator)

Are there accumulators with all the above properties?

The intended use case is a public blockchain without a "super user"/"admin"/"authority" managing the accumulator. In particular, witnesses should be publicly verifiable, accumulator updates (additions and/or deletions) should be public, and witnesses should be updatable from publicly broadcasted auxiliary information.


texts: Does the Initialization Vector in DES have to be 8 bytes long?

texts: I was experimenting around with DES and decided to implement an IV (Initialization Vector) for it. I noticed that in DES, which is 56 bits and 8 parity bits, the IV would be 8 bytes in length. Does that mean that if I were to program DES but using a 128-bit key, the IV would be 16 bytes in length instead of 8 bytes in length? (Cryptography Rookie here)


texts: Can Galois/counter mode be used for stream ciphers (Galois/stream mode)?

texts:
The authenticated encryption mode of operation Galois/counter mode has recently gained acceptance because of its high performance due to its inherent parallelism and no pipeline stalls. It requires a block cipher having 128 bit block length which is used in counter mode, and authentication is done by using multiplication in the Galois field GF(2128).

However, some ciphers are stream ciphers instead of block ciphers. Could the block cipher used in counter mode be replaced with a stream cipher in the Galois/counter mode? Of course, it could not be called Galois/counter mode then due to not employing a counter. I think it could perhaps be called Galois/stream mode.

My initial intuition based on the picture at Wikipedia is that since the block cipher in this mode of operation is only used to encrypt an incrementing counter, a stream cipher could be used, with its output stream packetized to 128-bit packets. However, I am not a cryptography expert, so such a replacement could result in some unknown form of weakness.

One difficulty would be how to obtain the hash key (a block of zero bits encrypted by the key). Perhaps the first 128 bits of the stream cipher output could be used as the hash key?


texts: Do q-ary lattices have parallelogram kind of structure?

texts:
An $m$-dimensional lattice is defined by a basis $A \in \mathbb{R}^{m \times n}$ is the set of points $\{Az : z \in \mathbb{Z}^n\}$. A picture of these points would be like a nice parallelogram kind of structure.

In crypto, we use $q$-ary integer lattices defined by basis $A \in \mathbb{Z}_q^{m \times n}$ and is defined as $\{x \in \mathbb{Z}^m : \exists z \in \mathbb{Z}_q^n, x = Az \mod q\}$. I couldn't imagine how these lattices look like. Do these also have the same kind of parallelogram structure? Why do cryptographers use these lattices?


texts:
As I understand to obtain a Golden Block is to finding a nonce that matches a hash lower than a given target, as shown in this research-gate article.

And here is a "py" kernel: Bitcoin mining python (Github)

As the nonce is only a 4 (8-bit)byte it is only to compare 65,536 hashes, that it seems ridiculous for any GPU.

So... Why is it difficult?


texts: Security implications of storing an ssh passphrase

texts:
I'm trying to understand the security implications of encrypting an ssh key with a passphrase, and storing the passphrase in the MacOS key chain or Gnome key-ring.

As I understand it, my ssh key passphrase needs to be long to prevent offline attacks (e.g., an attacker getting access to un-encrypted backups).

The operating system key-ring is encrypted using using my login password (OSX, gnome-keyring). The password normally isn't long (compared to a passphrase) as the operating system rate limits login attempts.

If I backup both my ssh key and my key-ring, have I reduced the complexity of cracking my ssh key from guessing my passphrase to guessing my password? Since it's implemented in both Gnome and MacOS and I haven't seen any warnings about this I feel like I must be wrong, but I'm not sure why.


texts: Setting up of polynomials for CP-ABE or KP-ABE Access Trees

texts: My question I guess is how the selection is done. A brief explanation with a simple access tree will be very helpful.


texts: What is the possibility of collision of trailing 160 bits of Keccak_256, for any two differing public-keys as pre-images?

texts:
Earlier today I was answering a question on the ethereum SE site that analyzed the potential for more than one private key on curve secp256k1 (which maps to a distinct public key) to control the same ethereum address which are derived by hashing the public-key with Keccak256 as a byte array, and whether the rightmost 160-bits of the two resulting distinct hash digest could collide and thus two different private keys control the same address.

In other words, what would be the possibility that any two Keccak-derived  hash digests had the same right-most 160 trailing bits (small-endian side)?

And secondly, does that possibility change (and to what degree) if both pre-images can only be valid secp256k1 public-keys of which there are roughly ${2^{256}}$ of them or more precisely n as per this curve's parameters, where n is equal to 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.

Again, ethereum addresses are simply the last 40-hex characters of a 64-hex (256 bit) Keccak Hash of the secp256k1 public-key derived from the users private key (assumed to be less than n).

If the digest space is $2^{256}$, and there exist even 2 digests that share the same trailing 160-bits, what are the chances that the pre-images to those 2 digests are valid 512-bit public-keys? And moreover, that those private-keys were actually derived by a private key known to the user (and not just a random 512-bit string that was brute-forced).

Given the multiple layers of conditions (compared being able to try any arbitrary pre-image regardless of length etc..), I was thinking that it could be possible (by chance perhaps) that no two private keys will derive the same ethereum address, even if there exists more than one Keccak256 hash-digest that partially collides in terms of the last 160 bits.

Although if there is a non-negligible amount of such 160-trailing-bit collisions, perhaps the chances actually exist for one ethereum address to be controlled by two different public keys? (even if not feasible to find them).

Note: My estimate/guess is that one would have to brute-force search at least $2^{160}$ valid private keys on the elliptic curve, including steps to derive the public key and resulting Keccak256 hash digest, to try to find even one such partial collision of the last 160-bits.

Can such a scenario even be computed or is there no way to know?


texts: Is there confirmation blocks in Proof-of-Stake Blockchain?

texts: When I'm reading literature about proof-of-stake blockchain, I found that it seems there is no concept about confirmation blocks (which is used to confirm a posted transaction is indeed honestly generated and in bitcoin we need 6 confirmation blocks that is enough). However, my question is that why we don't need confirmation blocks in Proof-of-Stake blockchain like Proof-of-Work blockchain?


texts: Show that there is an efficient zero knowledge proof for any language $L \in NP$

texts:
Let $(P,V)$ be an efficient zero-knowledge interactive proof for some language $A \in NP$ that is $(T,\epsilon)-\text{sound}$ and $(T,\epsilon)-\text{ZK}$.
I want to show that for every language $L$ that is reducible to $A$ there is also such an efficient zero-knowledge interactive proof $(P_2, V_2)$ which is also $(T,\epsilon)-\text{sound}$ and $(T,\epsilon)-\text{ZK}$.
Well, I am not sure how exactly to start to describe such $(P_2, V_2)$, but maybe I don't understand this completely since it seems there is only one straightforward way.
Since $L$ is reducible to $A$, then there is a Levin reduction from $L$ to $A$. Namely, there is a polynomial algorithm $R$ such that $R(x) \in A \leftrightarrow x \in A$, and there is a polynomial algorithm $W$ that maps a witness $w$ for $x \in L$ to the witness $W(x,w)$ for $R(x) \in A$.
My idea was to take the proof system $(P,V)$ and for the input $x$ apply $R(x)$ to simulate the original zero-knowledge proof for $A$.
However, it seems too trivial to me. Moreover, in this way I only get $(T-|R|,\epsilon)-\text{sound}$ and $(T-|R|,\epsilon)-\text{ZK}$, since I need to run the algorithm $R$.
Help Would be appreciated.


texts:
Given a SHA1 hash, is it now possible to "practically" find the source material that was passed through SHA1 now that the Shattered paper has produced the first "practical" collision?

As a follow on question - if I have the SHA1 Hash and the Source document, can I find/produce the 2nd document using the Shattered algorithm, if I know in advance that it exists?


texts: NIST Diffie-Hellman prime: how was it picked? Where did it come from?

texts:
According to this Matasano Crypto challenge, the NIST "likes" the following prime modulus, which appears to be expressed in hexadecimal:

  ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff

I have a few questions about it:

Is this number specified anywhere? I tried Googling it, both in decimal and in hexadecimal, hoping to find it somewhere, maybe in a NIST document, but I couldn't find it anywhere.
Why was this particular number picked? I know that Diffie-Hellman requires a prime modulus, and it should be big enough to prevent certain factoring attacks, and it should also be a safe prime, also to prevent certain factoring attacks, but there are lots of numbers with these properties. Was that number chosen somewhat arbitrarily, or were there any other criteria used to pick it?
Is this number used for anything other than Diffie-Hellman, like maybe RSA or elliptic curve algorithms?


texts: Proving equality of two Schnorr Signatures

texts:
Given two Schnorr Signatures that were made from the same $x$, where each $x$ is private. Is there a way to prove that they came from the same $x$ without revealing $x$?
I heard about Chaum-Pedersen Protocol and how it is supposed to address this, but I am a bit confused how it should work. The book I'm reading has the following notation:
Equality is proven so long as:
$r_1 == g^{s_1}$. $y_1^{c_1}$
and
$r_2 == h^{s_2}$. $y_2^{c_2}$
Where $g$ and $h$ are generators
$s$ is the proof
$y_1$ and $y_2$ are the public keys of the the secret $x_1$ and $x_2$
and $c_1$ and $c_2$ are the challenges
I am seriously confused about what the relation between those numbers are: With the above, you prove that each Schnorr Signature came from a different $x$, but not that they came from the same $x$, right?
Answering some questions that came up:

Are $g$ and $h$ different generators from the same group?

Yes, they are.

Are $c_1$ and $c_2$ hashes?

Yes they are. Made with a random oracle. The term "challenge" might be weak here since they are non-interactive.
I'm just really trying to wrap my head around the possibility of proving equality for Schnorr signatures.


texts: If I concatenate two colliding SHA-256 messages with the same prefix and suffix, will the resulting hash output still collide with each other?

texts:
So let's say that there are two messages, $x_1$ and $x_2$, which hash to the same output. In other words, these two messages collide with each other:

$$\operatorname{SHA256}(x_1)=\operatorname{SHA256}(x_2)$$

Questions:

Now, let's say I append identical prefixes and/or suffixes to both $x_1$ and $x_2$:

$$\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)\text{ and }\operatorname{SHA256}(p\mathbin\|x_2\mathbin\|s)$$

Now, will $\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)=\operatorname{SHA256} (p\mathbin\|x_2\mathbin\|s)$ as well?
Considering another slightly different scenario here - a partial collision rather than a full collision.

Let's say $\operatorname{SHA256}(x_1)$ collides with $\operatorname{SHA256}(x_2)$ in the first 80 bits.

Now, if I add identical prefixes and suffixes to $x_1$ and $x_2$:

$$\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)\text{ and }\operatorname{SHA256}(p\mathbin\|x_2\mathbin\|s)$$

Will  $\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)$ still collide with  $\operatorname{SHA256}(p\mathbin\|x_2\mathbin\|s)$ in the first 80 bits as well?


texts: Is there such a thing as perfect CPA security?

texts:
Consider the following experiment.

If we require that $$\operatorname{P}\left( \mathcal A \text{ succeeds} \right) = \frac{1}{2}$$ for any adversary $\mathcal A$ in order to call the scheme $\Pi$ perfectly CPA secure, can such a scheme exist?

It would seem like this definition cannot be met since the adversary can use the oracle access to compute $\text{Enc}_k(m_i)$ for $i=1,2$ as many times as necessary until one of them coincides with $c\leftarrow \text{Enc}_k(m_b)$, at which point $\mathcal A$ knows what $b$ is. Is my thinking correct?


texts: Taking $p$ and $q$ to be the same value in paillier cryptosystem

texts:
I was implementing Paillier cryptosystem when I came across the fact that as soon as I take the primes $p$ = $q$, I start getting incorrect decryption results.
As far as I can understand, when I take $p$ = $q$, the function $L(x)$ returns a fractional value instead of an integer one, meaning that in case when the primes are equal $L($$g^{\lambda}$ mod $n^{2}$) is not an integer. I also get that when the primes are equal, then $\lambda = (p-1)$, since lcm of $(a, a)$ is $a$.
Can someone explain that where do things go wrong when the primes are equal?
Reference for the scheme


texts: Can a digital cash scheme exist that is anonymous and offline using blind signature and anonymous signature?


texts:
Is there a well maintained, preferably documented, Sigma protocols compiler library? i.e. takes an abstraction of statements to prove, and outputs a cryptographic protocol between verifier and prover?
A search yielded that paper, but it seems to point a library in which I don't find any code.


texts: Proof that pseudo-random generated key is semantically secure

texts:
Let $G: \{0,1\}^s \rightarrow \{0,1\}^r$ where $r > s \;$  be a secure pseudo-random generator.

Let $\xi = (E,D)$ a semantically secure cipher whose key space is $\{0,1\}^r$

Let $\xi' = (E',D')$ a cipher whose key space is $\{0,1\}^s$ and such that:

$E'(k, m) = E(G(k), m)$
$D'(k,\;c)\; = D(G(k),\;c)$

How can I prove that $\xi'$ is semantically secure?

I guess that I should use the fact that a semantically secure cipher uses a random key, so using a pseudo-random key would add just a negligible advantage for the adversary to guess the key, so the sum of the semantically secure negligible advantage and the pseudo-random key negligible advantage would also be negligible, but I'm not sure how to build a proof.


texts: Speeding up partially known plaintext preimage recovery attack on MD5

texts:
Suppose there are three messages A, B and C of different length, that are 16 DWORDs in length when combined. I know the plaintext and length of A and C, and only length of B. Is it possible to take any advantage of this knowledge when trying to recover a preimage of MD5(A || B || C)? I'm targeting "raw" MD5 transform, as C is in fact padding and bitlength, so I feed it with 16 DWORDs of input and expect to get 4 DWORDs of digest back.

A is 8 DWORDs in length, and B and C are 4 DWORDs in length each.

I can only think of precomputing first round as much as possible as long A message is used, but that does not give that much speedup. Any metacompilation techniques?

UPD1: I have the following idea, but I'm unsure if it has any value in this context and in general. I would greatly appreciate review of it.

It's possible to express each DWORD as collection of independent bits, each possibly being in three states - set (0), unset (1) and upset unknown. All unknown bits have their unique ID, and hold up their creation history - as result of XORing two unknown bits is also unknown, we spawn more unique unknown bits when necessary. It's possible for unknown bit to be "determined" by ANDing it to 0 or ORing to 1, so the outcome is no longer unknown. Also XORing it to itself would make it 0, while XORing unknown bit to it's inverted counterpart will make it 1, and so on.

Rotation has no effect on bits themselves, only on their order in the "DWORD collection". Bitwise operations for DWORDs scale down to bits in obvious manner, and addition is expressed through ADD operation, which returns result and carry bit, which is in turn ignored when adder's result is the MSB.

After such tracing or 'metacomputation' we will end up in directed graph having 128 unknown input bits (message B) and 128 output bits of digest hardly twisted and entangled with input bits. Each node of graph is operation (XOR, AND, OR, NAND, NOR, NOT, ADD etc), incoming edges will be arguments to these functions, outgoing edges are results. Symmetrical transitive binary operations can be extended to arbitrary arity using behavioral definition like 'if any of the arguments is set, result is also set' for OR, or 'invert result of XORing all the unknown argument bits if XORing known bits together produces 1' for XOR.

So first idea is to try to simplify this graph using rules expressed above as much as possible, then unwind each bit's history, revealing long expression of AND/OR/XORs making use of initial unknown bits from B message, and try to find common chains of operations that may be computed at once. Problem with this approach is that I overcomplexify calculations 32 times, as DWORDs are breaked down into bits... Maybe there is way to somehow bond them back, producing some function taking B message candidate and returning single DWORD in most compact way? I don't know. Also I don't know if I can use the same approach but with DWORDs instead of bits at the lowest level.

Second idea is to try to reverse this graph, feeding desired MD5 output into "output unknown bits" and trying to figure out what arguments were to produce such results - for example, if OR(A, B, C, ...) == X, while X being unknown bit revealed to be zero, it's impossible for A, B and C (and others) to be anything but zero, so propagation can proceed. Same applies to AND(A, B, C, ...) == X, where X is set - A, B and C have to be all set. For ambigous cases branching should occur, pushing current graph state into stack, selecting one of possible argument layouts and proceeding until first conflict - e.g. for example according to one expression unknown bit should be unset, and according to other expression same bit should be set, this means one of possible paths previously selected was wrong and next should be tried.

So, as this hadn't implemented already, something is wrong with it. What exactly is wrong? I think it may figure out that time needed for walking through all the branches exceed bruteforce time, but I'm not sure.


texts:
Let's say I generate a keypair for a user with go's ed25519 package:

pub, private := ed25519.GenerateKey(nil)

And I want to generate additional child keys as signing identities for my user. Is it more secure to not use that public key created at initial generation and instead derive a new child private key as a signing identity? Or is creating another child key exactly as secure as using the public key created at generation?


texts:
The signature format for ECDSA signatures can be encoded using ASN.1 integers according to X9.62 or it can comprise of two integers with the same size as the key size.

In case the X9.62 format is used is it mandatory to use DER encoding (distinguished encoding rules) of the result, or is BER encoding (basic encoding rules) also acceptable?


texts: Public Key Cryptography: Diffie-Hellman Key Exchange

texts:
Please watch this video it's very short. If you already know cryptography and really good at it please start from 3:51.

I didn't understand the step at 4:39, can someone here to explain?

Why is $16^{54} \mod 17$ is equal to

$3 ^ {24\times54} \mod17 \equiv 1$?

He just wrote that. Alice didn't knew bob's private number how did he raised $3 ^{24}$?


texts: Is the practice of "security through obscurity" violating Kerckhoffs's second principle?

texts:
Security through obscurity is the reliance on the secrecy of the design or implementation as the main method of providing security for a system or component of a system.

Kerckhoffs's second principle:

  "It should not require secrecy, and it should not be a problem if it falls into enemy hands"

As stated here in the section "Security through obscurity":

  "It helps, I think, to go back to Kerckhoffs's second principle, translated as "The system must not require secrecy and can be stolen by the enemy without causing trouble," [...]. Kerckhoffs said neither "publish everything" nor "keep everything secret"; rather, he said that the system should still be secure even if the enemy has a copy."

But isn't the practice of security through obscurity still violating Kerckhoffs's second principle per definition?

And why are people even practicing security through obscurity if it, as stated, doesn't provide more security?


texts: Is post-quantum Oblivious Transfer possible

texts:
If I’m not mistaken classical OT is not regarded quanum-safe. However I’ve been reading (not really understanding) some papers [1,2] and some reviews[3] on quantum OT and/or post-quantum OT, it seems to be possible.

I do have an engineering background, so that’s the reason why I don’t get quantum cryptography papers.

Can you please explain briefly in layman (engineer) terms if and how post-quantum OT is possible?

[1] https://www.computer.org/csdl/proceedings/phycmp/1994/6715/00/00363696.pdf

[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.650.385&rep=rep1&type=pdf

[3] https://www.quantiki.org/wiki/oblivious-transfer


texts:
I often heard about private key storage, but rarely about key life cycle in memory.

For example, when SSL is used from one peer, the private key is used to sign messages or decrypt other peers' messages, so it has to be in memory as long as the http process goes on.

It may raise some security issues that clear private key is in memory for days and days ?
Is that right or I missed something (master key, ...) ?


texts: What signature aggregation schemes support valid single signature is exist in aggregation signature?

texts:
For example, there are three signers, A, B, C:

A: PK(a) SK(a) MessageA SignatureA
B: PK(b) SK(b) MessageB SignatureB
C: PK(c) SK(c) MessageC SignatureC

and generate a signature aggregation : SignatureAgg.

Is exist a method to check that if SignatureB contains in SignatureAgg, and do not know SignatureA and SignatureC.


texts:
I am considering two login procedures, both via HTTPS GET API:

procedure A:

Reuqest:

https://host/login?id={identity}&time={client_timestamp}&nonce={ramdon_string}&sign={signature}

Response:

{"stat": 0, "token": "token_string"}

Where:

id: identity of the request client, which is public (a hardware identity printed on label)
time: unix timestamp of the client, which must be in-sync with server clock (with allowed error about +/- 5 minutes). This is added to prevent replay attack.
sign: an hmac-sha256 of nonce+time+<shared-secret>.  nonce is saved at server-side for a period of time, within which re-use of same nonce is not allowed.

procedure B:

Request:

https://host/login?id={identity}

Response:

{"stat": 0, "token": "encrypted&base64 encoded token"}

In this scheme:

server will generate a token (if id is valid), encrypt <token><salt> with shared-secret using AES cipher.
server will lookup cache to prevent re-encrypt of same token. The cache will be valid for a period of time to save server CPU resource.
client will decrypt the token using shared-secret and use the first N byte as token (token length is pre-defined).

My question is, considering that the channel is HTTPS, encryption key is pre-shared, which procedure is considered more secure, and why?  Thanks.


texts: If you XOR a random input with a biased input, the output is random - why?

texts:
Ive seen in an answer to this question here :

https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes/5889288#5889288

that If you XOR a random input with a biased input, the output is random .

What is the reason for that ?
Is there a formal proof ?

thx