texts: In 2020, SHA-1 practically broken in chosen-prefix collision (CP-collision). Can double SHA-1 hashing prevent CP-collision?

texts:
In a recent study SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust by Gaëtan Leurent and Thomas Peyrin. 2020, they showed the first practical chosen-prefix collision attack that required two months of computations using 900 Nvidia GTX 1060 GPUs.

Chosen-prefix collision (CP- collision)1: two message prefixes $P$ and $P'$  are first given as challenge to the adversary, and his goal is to compute two messages $M$ and $M'$ such that $H(P \mathbin\| M) = H(P' \mathbin\| M')$ where $\mathbin\|$ denotes concatenation.

They worked for two kinds of attacks;

They reduced the use of neutral bits BCJ+05 and boomerangs JP07 from $2^{64.7}$ to $2^{61.2}$
Also, they improved graph-based technique (LP19) to compute CP-collision from $2^{67.1}$ to $2^{63.4}$.

Actually, the CP-collision attack enables attackers to create some meaningful messages; however, classical collisions are not.
To demonstrate the attack they achieved a PGP/GnuPG impersonation (CVE-2019-14855).
The list of attacks on SHA-1

2005, collision with complexity $2^{69}$, Finding collisions in the full SHA-1, Wang et. al.
2013, chosen-prefix collision with complexity $2^{77.1}$, New collision attacks on SHA-1 based on optimal joint local-collision analysis, Stevens et. al.
2013, collision with complexity $2^{64.7}$, from the previous article.
2016, free-start collision with complexity $2^{57.5}$, Freestart collision for full SHA-1. Stevens et. al.
2017, collision with complexity $2^{63.1}$, The first collision for full SHA-1., Steven et. al.
2019, chosen-prefix collision with $2^{67.1}$ complexity, From collisions to chosen-prefix collisions, Leurent et.al.
application to full SHA-1
2020, collision with $2^{61.2}$ complexity, SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust, Leurent et. al. (The new article)
2020, chosen-prefix collision with  $2^{63.4}$ complexity, same paper above.

Questions:

Can a double hashing $h= \operatorname{SHA-1}(\operatorname{SHA-1}(m))$ mitigate the CP-collision?* It seems so, since the meaningful part will not exist for attackers as longs as they are not able to break double $\operatorname{SHA-1}$. This seems not feasible, yet.
An immediate follow-up question; if the answer is yes, should we design the new protocols based on double hashing?

*There can be many variants of double hashing.


texts: Encrypt multiple RSA keys with same passphrase

texts:
I have to create and store a bunch of RSA key pairs with openssl. The private keys will be encrypted with the aes256 option and a very long, random password.

Would it be safe to use the same password for all keys? Or is it better to encrypt every key with a different password?


texts: Adding a Random component to CBC MAC in order to enlarge the tag space

texts:
CBC MAC that is using AES as the underlying block cipher, has tag space of 2^128. If we add a random single block, concatenating it with the tag, and encrypt it again in AES CBC mode, with additional key, we get a 256 bit tag of 256 bits space:

TAG = CBC_MAC(K2,CBC_MAC(K1,M)||r) || r

(where r is 128 bit random number) This is a randomized MAC generating tags in the space 2^256. In the same way we can easily generate tag in any size. Is there any standard that is using this method?

Thanks


texts: How can I obtain a code with same weight codewords?

texts:
I want to implement "A new one-time signature scheme
from syndrome decoding". My first challenge is how to obtain $P$. $P$ is a generator matrix whose codewords have weight not exceeding an integer value $w$. How can one obtain this matrix for practical security parameters? Do you have any advice?


texts: How OR gates are garbled in recent optimizations techniques like free XOR, Half Gates?

texts: I am a research student and I have been studying garbled circuits, specifically its optimization techniques. However, in every research paper i have encountered, the researchers have only shown how to garble an AND gate and XOR gates. The circuits do contain OR (or don't they?), my question is how an OR gate will be garbled in Half gates and Free XOR techniques scenario? Any help in this regard would be highly appreciated.


texts: How to verify a shared secret using only AES?

texts:
I have two devices that need to verify that they both are in possesion of the same secret key. One of the devices is a very limited embedded device that only has AES128 available, no SHA or other hash variants.

My idea is a basic two-way challenge-response scheme:

Device 1 generates 8 bytes of random data (C1), and sends it to Device 2
Device 2 generates 8 bytes of random data (C2), and calculates R1 == AES(key, C1 || C2)
Device 2 sends R1 and C2 to Device 1
Device 1 calculates AES(key, C1 || C2) and verifies that this matches R1
Device 1 calculates R2 == AES(key, R1)
Device 1 sends R2 to Device 2
Device 2 calculates AES(key, R1) and verifies that this matches R2

Or put another way:

D1->D2: C1
D2->D1: C2, AES(key, C1 || C2)
D1->D2: AES(key, AES(key, C1 || C2))

My thinking is that this is a form of CBC-MAC, where each device offers a random challenge to the other that prevents replay attacks. Since it's just one block of data being processed, the CBC-MAC weaknesses aren't a problem.

Is this a sensible way of verifying the shared secret, or should I be doing something different?


texts:
I've been given as an exercise to show an encryption scheme that is CCA-secure but is not a secure message transmission scheme.

What is a message transmission scheme, and how does it differ from a regular encryption scheme?


texts:
I have a question about RSA key generation.

This is a simple RSA algorithm:

Choose p = 3 and q = 11
Compute n = p * q = 3 * 11 = 33
Compute ?(n) = (p - 1) * (q - 1) = 2 * 10 = 20
Choose e such that 1 < e < ?(n) and e and n are co-prime. Let e = 7
Compute a value for d such that (d * e) % ?(n) = 1. d=3
Public key is (e, n) => (7, 33)
Private key is (d, n) => (3, 33)

So public and private keys are numbers. but in many online encryption websites keys are like this:

d94d889e88853dd89769a18015a0a2e6bf82bf356fe14f251fb4f5e2df0d9f9a94a68a30c428b
39e3362fb3779a497eceaea37100f264d7fb9fb1a97fbf621133de55fdcb9b1ad0d7a31b379216
d79252f5c527b9bc63d83d4ecf4d1d45cbf843e8474babc655e9bb6799cba77a47eafa83829647
4afc24beb9c825b73ebf549

How are those keys actually generated?


texts: I am currently working on a Koblitz curve. I have found the curve has two matching groups based on the base curve point and N-1 point. My question is as follows: Is there an algorithm to determine how many X coordinates are the same in an elliptic curve? This will tell me how many groups are inside the entire curve based on its parameters given.


texts:
In the key generation algorithm of cp-abe there are attributes: $x_1, x_2,...x_n \in \{0,1\}^*$

$r, r_{x_1}, r_{x_2},...r_{x_n} \xleftarrow{R} Z_p$ are chosen randomly to generate the private key $SK$ where.

$SK = [g^{\left(\alpha+r\right)/\beta},
g^r \cdot H(x_1)^{r_{x_1}}, g^{r_{x_1}}, ...,
g^r \cdot H(x_n)^{r_{x_n}}, g^{r_{x_n}}]$

My question is, are those random $r's$ randomly chosen by the key authority each time a user requests a private key for certain attributes or is it generated once for all users and each user will be given the private key based on their attributes.

To be more clear assume user A claims attributes $x_1, x_2$ while user B claims $x_1, x_3$. They both at different times request a private key containing a component for attribute $x_1$. So is $r_{X_1}$ generated once for each user request or is it the same for both requests? Of course $g^r \cdot H(x_1)^{r_{x_1}}, g^{r_{x_1}}$ will be affected as well if they are different.


texts:
Suppose that Alice has a secret bit $a$ and Bob has a secret bits $b_1,b_2$ and that Alice and Bob want to compute the function $h(a,b_1,b_2)=b_1 \wedge (b_2 \oplus a)$ using Yao's Garbled Circuit protocol.

a) Suppose that Alice selects two random permutations $\pi_1, \pi_2: \{(0,0),(0,1),(1,0),(1,1)\} \to \{(0,0),(0,1),(1,0),(1,1)\}$. Write down the garbled circuit that Alice sends Bob.

b) Suppose that Alice is malicious, but Bob behaves honestly during the execution of the protocol. Write down a garbled circuit that Alice can send Bob to extract the secret bit $b_1$ directly.

I was able to work out complete part (a), but I can't wrap my head on how to deal with the fact Alice is malicious. When she is malicious,

She does not garbled the circuit at all or for $h$.
She can stop midway in the garbling process
She can not return Bob query about his bit.

Can someone help me understand this?


texts: Is there way to combine secrets first and later split them?

texts:
Shamir's Secret Sharing allows a secret to be split into multiple shares so that it can be reconstructed later.

Is there a way to do the reverse? Can we combine a few secrets first and later split them into their original forms? More clearly: given two strings I want to "pack" them into single secret and later split them into respective strings. (I'm not sure how this would be called in literature.)

The simplest solution I could think of is concatenating all of the secrets and storing their relative positions, later string splitting them based on their positions. This would be too naive and there is no space advantage.


texts: How can I follow the validation and verification recommendations of the NaCl (sodium) secretbox library?

texts:
I was advised to use crypto_secretbox_xsalsa20poly1305 due to its simplicity and because it's safe against timing attacks. I'm reading the secretbox tutorial, and there's a link to Validation and Verification regarding message length. In that, in the last paragraph, it says the following:

  Tests are currently limited to 4096-byte messages. This is one of several reasons that callers should (1) split all data into packets sent through the network; (2) put a small global limit on packet length; and (3) separately encrypt and authenticate each packet.

Now I don't understand who's the "caller" here. Is it me in my application or the NaCl library? From requirement (1) it seems it's me. From requirement (3) it seems it's NaCl, because I don't have control on separating encryption and implementation, because both happen in one call of crypto_secretbox_xsalsa20poly1305.

So I guess my question is: If I have a message whose length is longer than 4096 bytes, should I manually split it when using crypto_secretbox_xsalsa20poly1305, encrypt and authenticate each, then combine them together in a certain way as my final cipher?


texts:
I wanted to know how I could manage to do what I'm going to tell you next, with the RSA encryption/decryption scheme.

So Alice and Bob each have a public key $(n, e)$ and a private key $(p, q, d)$; where $n = p\cdot q$; $p$ and $q$ are odd distinct primes; and $e\cdot d \equiv 1 \pmod{\varphi(n)}$ with $1 < d < \varphi(n)$.

Alice has a number $x$, she encrypts it with her $e_A$ and sends it to Bob; this way, Bob cannot tell which number it is. Then Bob encrypts it with his $e_B$ too and sends it back to Alice.

I want Alice to be able to decrypt the number from Bob; this way, Alice would obtain the number $x^{e_B} \bmod n_B$ and Bob could still decrypt it with his private key to find $x$ again.

So basically, I want to find a way to make the number comes back to Alice but I don't want her to be able to know which number it was first (and Bob could still decrypts it).

I hope I was clear enough and sorry for my bad English.

Thank you.


texts: Is F_k_1(x) \xor F_k_2(x) a pseudorandom function?

texts:
I'm trying to determine if $F_{k_1, k_2}(x) = F_{k_1}(x) \oplus F_{k_2}(x)$ ($k_1 \neq k_2$ because that would be lame) is a pseudorandom function. My hunch is that it is. My reduction proof proceeds like this (but I get stuck halfway through)

Suppose $F$ is not secure. Then there is a PPT distinguisher D' s.t. for all $negl(n)$ we have:
$|P(D'^{F(\cdot)}(1^n) = 1) - P(D'^{f(\cdot)}(1^n) = 1)| \geq negl(n)$

We then construct a distinguishers $D_1, D_2$ that break $F_{k_1},F_{k_2}$.

So $D_1$ gives a message m to oracle $O_1$. $D_1$ wants to find out if $O_1$ is random or if it is actually $F_{k_1}$. It receives back output $y_1$. It then asks D' if $y_1 = F_{k_1}(m) \oplus F_{k_2}(m)$. If D' says yes then we know that either $F_{k_2}(m) = 0$ or $O_1$ is random since:

$0 = y_1 \oplus y_1 =$ $F_{k_1}(m) \oplus y_1 $ $= F_{k_1}(m) \oplus F_{k_1}(m) \oplus F_{k_2}(m) = F_{k_2}(m)$.

Since we learn something about $F_{k_2}$ which can be used to break $F_{k_2}$.

Working symmetrically we can learn something about $F_{k_1}$.

Basically if you run both tests, and D' says that both $y_1$ and $y_2$ are
$F_{k_1}(m) \oplus F_{k_2}(m) $ you can check if either $y_1$ or $y_2$ are 0. If neither are 0, both oracles must be random.

Am I on the right track with this? How would I write up a formal proof?


texts: How can I exploit the structure of the secp256k1 prime for fast arithmetic?

texts:
I'm implementing logic on an FPGA (programmable chip) that does the key verification part of ECDSA on the curve secpk256k1, in which all operations are mod p where $p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$ (a Mersenne prime).

I'm starting with building a circuit to do the modular reduction, I know about Barret's and Montgomery's algorithm, but I have been reading in several guides that because of the $2^n - c$ form, as well as it being a Mersenne prime that there are simpler ways to do the modulo reduction.

But I'm getting stuck on understanding the actual logic underneath this, I was wondering if any one have any good example or pointers to understand how to do this modulo operation a bit better?

There was a similar question here (except I'm doing this on FPGA not CPU, so the word size is irrelevant) but I don't totally understand the answers reply, so even just some helpful comments explaining the same thing would be a huge help. Fast modular reduction

This paper also has a fast implementation on page 7 (http://cse.iitkgp.ac.in/~debdeep/osscrypto/psec/downloads/PSEC-KEM_prime.pdf) which looks like it came from one of these optimizations above, but I would like to try understand how to get there myself.


texts: How to use Libsodium encryption (in PHP) in the most secure possible way?

texts:
In a PHP project in which fool-proof encryption is fundamental, I'm using the Libsodium library.

Hope you guys can shine some light on the following questions.

For all of the following functions, it looks like the length of the encrypted message is directly proportional to the length of the unencrypted message:

sodium_crypto_secretbox
sodium_crypto_box
sodium_crypto_box_seal

It looks like no padding is used by default, correct ?
This means that if within my setup I use different types of messages which each have a different length, an attacker can easily derive what kind of message it's about (without however knowing the content of the message), right ?

To mitigate this risk, I want to implement padding and I am looking for some advise on how to do this.

Is appending a random length random content (using random_bytes) message to the unencrypted message a good idea ? Does it make a difference whether I append it to the end of the message, at the beginning of the message or somewhere in the middle (or a combination of all) ?
Are there more efficient ways to do this ?
If part(s) of the unencrypted messages are known, is it possible for an attacker to crack the encryption ? Or does it somehow becomes easier to do so ?

Example: if each encrypted message contains data delimited by for example "," or if each message starts/ends with a certain string or contains a certain string somewhere in the message, does this make attacks easier ?
I mean, even when using padding an attacker might still know for sure part of the message's content.

I previously asked a question about how safe the encryption is (How safe are Libsodium Crypto Boxes?). Someone replied that 2^128 tries would be required to crack it. Does the amount of tries decrease if part of the message is known ? If yes by how much does it decrease ?
What if someone knows the entire unencrypted message (for example the receiver) ? How easy/hard would it be for him to crack the senders' secret key ?
What about signed messages in Libsodium ? I know that signing does not encrypt the message but only appends a signature to it. How easy/hard is it to crack a SK based on a signature ? Could the receiver of a signed message potentially create a valid signature for a message not created by the sender ?
I read that nonces can be public without a problem. Nonetheless, does the fact that an attacker is in the possession of the nonce of a message decrease the cracking difficulty ?
Is it a good idea to change keypairs periodically to increase security ? Or doesn't this make sense ?
Does multi layer encryption make sense ? For example putting a crypto box inside another crypto box (with different keypairs off course). Or is this a bad idea ?
What about timing attacks ? I read that the time needed to decrypt/encrypt a message might give some clues about the SK. If Bob wants to crack Alices' SK, can he do so by analyzing how long it takes him to decrypt her message ? Or does it at least decrease the difficulty to do so ? If yes by how much ?


texts: Efficient setup for a Montgomery multiplication

texts:
Montgomery described an efficient method to compute a modular multiplication. This works by using a special constant $R$ and assumes the inputs $a$ and $b$ have been made into a special representation (residues $aR\mod N$ and $bR\mod N$) and produces the value $abR^{-1}\mod N$. Thus to pursue the computations, one needs the value $ab$ to be also in the special representation, which requires an additional (Montgomery) multiplication with the constant $R^2\mod N$.

This is especially useful to compute modular exponentiations with a large modulus $N$ and a big exponent such as in RSA.

Every step such as computing the special representation of $a$ and $b$ are costly, and so is the computation of $R^2\mod N$ (note that it has to be computed once, but still is costly).

What are the different ways to do the computation of $R^2 \mod N$ efficienty?


texts: Are common (secure) stream ciphers CCA1-secure?

texts:
My latest question and especially Ricky Demer's comment on the answer got me thinking: This homomorphic tranformation of RSA is most likely IND-CPA and maybe even IND-CCA1, but if it could be IND-CCA1, so could be a stream cipher in theory. This is especially interesting if you consider RSA-KEM paired with an unauthenticated stream cipher. Practically this would most likely also imply a simple standard construction for an XOR-homomorphic IND-CCA1 cryptosystem. This would also imply a post-quantum secure IND-CCA1 scheme with a partial homomorphism: McEliece as a KEM paired with a stream cipher (which is basically McBits minus the authentication).

So the question naturally follows:
Are common (unbroken) stream ciphers CCA1-secure?
Or formulated differently if CCA1-security isn't a thing: Are stream ciphers secure against non-adaptive chosen ciphertext attacks?

With "common" stream ciphers I mainly mean secure block ciphers in CTR mode and cipher such as ChaCha20 and Salsa20/20.


texts:
I have a question from my teacher: "Why can a symmetric encryption algorithm be considered a pseudo-random number generation algorithm?

Can anyone explain it to me?

And sorry if my english is not good!


texts: RSA: Construct private / public key for given cipher and plain text message

texts:
let's say we are given a classical RSA encryption scheme, though we would like to "reverse" the task:

Given two messages $c, m$ choose $p, q, e$ such that $p, q$ are prime and $c ^ d \equiv m\pmod N$ with $d \cdot e \equiv 1 \pmod{(p - 1)(q - 1)}$; $N = p \cdot q$.

I was wondering how one could approach this problem? Is it even possible for some large N?

Also does the conditioning improve if we loosen the constraints of classic RSA, i.e. $GCD(e, LCM(p-1,q-1)) \neq 1$? On another question I have read, that it is possible to construct message collisions, if the parameters are ill-formed, i.e. the condition $GCD(e, LCM(p-1,q-1)) = 1$ is not satisfied. I thought it to be related, though I could not retrieve the information of how such an collision could be achieved (or if it is even feasable).


texts:
I am also wondering why the three registers in a Trivium were chosen to be of different lengths. Was there a reason behind the decision?

Bob


texts: how is the rsa $publickey(n ,e)$ transformed into a textfile allowing its public distribtution?

texts:
wikipedia says about the keys itself:

  The public key consists of the modulus n and the public (or
  encryption) exponent e. The private key consists of the modulus n and
  the private (or decryption) exponent d, which must be kept secret.

I know, that public keys look like that in the wild:

  -----BEGIN RSA PUBLIC KEY-----
  MIIBCgKCAQEA+xGZ/wcz9ugFpP07Nspo6U17l0YhFiFpxxU4pTk3Lifz9R3zsIsu
  ERwta7+fWIfxOo208ett/jhskiVodSEt3QBGh4XBipyWopKwZ93HHaDVZAALi/2A
  +xTBtWdEo7XGUujKDvC2/aZKukfjpOiUI8AhLAfjmlcD/UZ1QPh0mHsglRNCmpCw mwSXA9VNmhz+PiB+Dml4WWnKW/VHo2ujTXxq7+efMU4H2fny3Se3KYOsFPFGZ1TN
  QSYlFuShWrHPtiLmUdPoP6CV2mML1tk+l7DIIqXrQhLUKDACeM5roMx0kLhUWB8P
  +0uj1CNlNN4JRZlC7xFfqiMbFRU9Z4N6YwIDAQAB

  -----END RSA PUBLIC KEY-----

or sth like:

   Subject Public Key Info:
       Public Key Algorithm: rsaEncryption
       RSA Public Key: (1024 bit)
           Modulus (1024 bit):
               00:b4:31:98:0a:c4:bc:62:c1:88:aa:dc:b0:c8:bb:
               33:35:19:d5:0c:64:b9:3d:41:b2:96:fc:f3:31:e1:
               66:36:d0:8e:56:12:44:ba:75:eb:e8:1c:9c:5b:66:
               70:33:52:14:c9:ec:4f:91:51:70:39:de:53:85:17:
               16:94:6e:ee:f4:d5:6f:d5:ca:b3:47:5e:1b:0c:7b:
               c5:cc:2b:6b:c1:90:c3:16:31:0d:bf:7a:c7:47:77:
               8f:a0:21:c7:4c:d0:16:65:00:c1:0f:d7:b8:80:e3:
               d2:75:6b:c1:ea:9e:5c:5c:ea:7d:c1:a1:10:bc:b8:
               e8:35:1c:9e:27:52:7e:41:8f

=> My question is, how are those numbers $n$ and $e$ transformed to a keyfile like above?

EDIT: Additionally, i was specifically wondering how the numbers are calculated into a keyfile. I mean, if I had a single really big number, i can imagine the number is easily converted into one of your encoding. But the public key is a combination of $n$ and $e$, and i don't know which combination.


texts: What are the differences between a digital signature, a MAC and a hash?

texts:
A message may be accompanied with a digital signature, a MAC or a message hash, as a proof of some kind.

Which assurances does each primitive provide to the recipient?

What kind of keys are needed?


texts: How reasonable is deriving the key a corpus of RSA-PSS signed messages?

texts:
Given access to a 2048 bit public key, a large corpus of 2048 bit plain text messages and their signatures (RSA-PSS with SHA256 as the hash and MGF)  are any of the following statements correct:

Increasing the number of of messages available significantly increases the likelihood an attacker can reverse the private key
Decreasing the plain text message size significantly increases the likelihood an attacker can reverse the private key

Note: by significantly I mean "before the heat death of the universe" becomes a few hundred years. If instead it becomes half the heat death of the universe, I'm less interested.


texts: Intuitively what makes indistinguishability obfuscation useful?

texts:
I am reading some papers about the application of indistinguishability obfuscators (IO). As far as I know, there are two techniques which enables the application of IO: shell game of secrets and punctured programs. It seems to me obfuscators are meant to make the program as close to a black box as possible, but it is known black-box obfuscation is not possible for some circuits.

I think the question is about how to force the adversary to learn by making queries. For example, standard PRFs are built upon black box model, and it is straightforward to prove the security based on some query complexity lower bound. To apply IO in the non-black-box case, PRFs are built to be puncturable to preserve functionality and randomness. Though I can follow the mathematical proof, I don't see why punctured PRFs along with IO makes the adversary see the program like a black box. Could anyone give me some intuition how IO programs differs from black boxes?


texts: I understand the general notion in play: if my laptop/computer is stolen or compromised I can revoke that particular subkey so (as long as people have updated their keys) they can't impersonate me. However, the compromiser can still read messages intended for me as far as I understand. So, maybe I don't lose signatures but if the thief has a way of intercepting messages intended for me (and if they have my laptop they very well might), they would be able to read them. Am I misunderstanding or is the creation of subkeys lest beneficial than some make it out to be?


texts: At what stage is DHE and RSA used during the SSL/TLS handshake?

texts: At what stage of the SSL/TLS handshake is the DHE and RSA used and what is the purpose of using a pre-master secret when you could just use RSA to exchange the symmetric key (i.e. AES) for further communications. I am confused how DHE, AES and RSA fuse into the SSL/TLS handshake process. Is there a handshake with purely RSA, purely DHE or both.


texts: How many bits of entropy are leaked for every derived password from a master?

texts:
Given a master password that has a lot of entropy (similar to Bitcoin HD wallet seed words, 130 bits of entropy or more) how many bits of entropy are lost per leaked generated password?

Let's take an example of the master password hello stack exchange good to see you and some passwords generated by PBKDF2 with SHA512 with 256k iterations using a tool I wrote

foo.com   mr7i?O5til?2
bar.com   PYOT1-AOhX.D
baz.com   rk!Vxf8G_HgO

Given an attacker has these generated passwords how much easier can they guess the original master password? How many if they have 2/3, 1/3, and how it compares to 0/3 as well?

Thank you!


texts: what is the fastest and efficient method to perform modular multiplication?

texts:
I'm working on a code that needs to perform modular multiplication of big numbers several times. Since the operation takes place several times, using division to find the remainder is very expensive. Repeated subtraction with the mod value also takes a lot of time because big numbers are involved.

The following commonly used modular multiplication algorithm is also slow

n = i
r = 0
for (bit = 0; bit < bitlength; bit++) {

    if (bitset(j, bit)) {
       r = (r + n) mod p
    }
    n = (n + n) mod p
}

So is there any other method to perform this quickly and efficiently?. I need expert advice on any alternative formula or shortcuts that can be used.


texts: Appropriate public exponent choice for RSA encryption

texts:
From what I understand, we can arbitrarily choose an exponent e as long as
 $\gcd(e,\phi(n)) =1$.

But what is the most appropriate choice for it?
Should it be small compared to $\phi(n)$ or approach it?


texts:
Can anybody explain in detail why repeating nonce is dangerous in CTR mode?

Two cases to explain

When plain text is repeated for each nonce.
When plain text is unique for each nonce

.


texts: What are KDF parameters in OpenSSL command-line utility for `enc`?

texts:
I refer to https://www.openssl.org/docs/manmaster/apps/enc.html and see that the only parameter for key derivation which I can set explicitly (not considering the obvious -S for setting salt) is -md which is MD to be used for key derivation algorithm.

Now the question is: what are other implicit parameters for KDF when using OpenSSL in cmd mode? In particular, does it use PBKDF2? And if so - the most important question: what is the default value for number of KDF iterations? I can't find those values.

I am using OpenSSL cmd utility to encrypt plaintexts. The result is decrypted using another crypto library. I need to test password-based encryption in particular.

To make it more clear: I want to save generated salts and passwords, then decrypt ciphertexts with another crypto library which does use PBKDF2 with HMAC_SHAxxx algorithms and gives the opportunity to set number of KDF rounds as well. So I want to have a possibility to derive exactly same keys from passwords and salts as OpenSSL cmd utility does.

Finally, maybe the idea to rely on cmd utility is somewhat bad considering my task. If so, I want to hear your opinion on this, too.

I've got OpenSSL 0.9.8zh 14 Jan 2016 (OS X).


texts: Relative merits of AES ECB and CBC modes for securing data at rest

texts:
I need to store several million Payment Card Numbers (PCNs) securely in a mainframe database (that is, 'at rest'). I assume that any attacker will have access to all of the stored data.

I assume the availability of a secure device that can:

Store a unique, constant ('master') key that is to be used for all
PCNs
If necessary, store a unique, constant IV to be used for all
encryption with the master key
Encrypt (AES-256) data in ECB or CBC mode
Decrypt (AES-256) data in ECB or CBC mode

What are the relative merits and demerits of the following possible options for encryption and decryption?:

Use the master key in ECB mode. I have heard/read that this is
cryptographically weak (Why?).
Use the master key and IV in CBC mode.
Prepend a 16-byte, microsecond-or-finer, timestamp to the PCN, then use the master key and IV in CBC mode. This would mean storing an additional 16-byte block of ciphertext, but this isn't a problem. On decryption, just discard the first 16 bytes of the resulting plaintext.
(If available) As (3), but have the device provide a 16-byte pseudo-IV.
Something better (please specify)

Extra kudos for explaining possible attacks on a large quantity of sixteen-digit numbers encrypted under any of these schemes.

I'm new at this, and I know it's very easy for noobs to produce stuff that an average cryptologist would find laughable, so please be gentle -- I'm just trying to learn.

I've placed this here, rather than on security.SE, because it looks like a better fit; if y'all disagree, I shall be most grateful if you will migrate it, rather than closing as off-topic.

For additional clarification, following the answer from @curious :

The reason I include ECB mode here is that it could allow me to save half the storage space. Since the messages are only one block long, I suspect this may affect the 'traditional' arguments against ECB.

But I am interested in understanding whether there are any specific vulnerabilities arising from:

The relatively low entropy of the messages (message space of 1E16 possibilities, reduced by PCN checksums)
The use of a fixed, universal key or key+IV


texts: What is the border between an ideal functionality and a protocol?

texts:
In the context of the UC framework, what is the border between an ideal functionality and a protocol?

It seems to me that it depends on the level of granularity required for proofs.

For example, the same protocol ${\Pi}_{1}$ may be described in more than one way:

${\Pi}_{1}$ requires parties to interact just with one ideal functionality ${F}_{2}$.
${\Pi}_{1}$ requires parties to interact with another protocol ${\Pi}_{2}$, that is equivalent to ${F}_{2}$, but it is explicit that it requires parties to interact with ideal functionalities ${F}_{3}$, ${F}_{4}$, ${F}_{5}$.

The only difference between the two cases is how detailed is the description of what ${\Pi}_{1}$ does. So, in general, ideal functionalities are a kind of terminal nodes in a graph of dependencies.

Does it make sense?


texts: How to determine RSA block size for decryption

texts: A message coded with RSA is broken up into blocks, then padded/transformed prior to encryption via modular exponentiation with the public key.  However, the encryption result for each block is not necessarily a fixed length of bits, octets or characters. What are the accepted protocols for delimiting these encrypted blocks so that they can be decrypted with the private key?


texts: Point at infinity for Jacobian coordinates

texts: Why is the point at infinity ∞ in affine space corresponding to (1 : 1 : 0) for Jacobian coordinates? How can this be shown? Is ist just to add the negative and see that the outcome is 1:1:0 or is there some "higher magic" to verify that a priori?


texts: Is there a quick method of listing certain elements of a cyclic group?

texts:
I'm studying applied cryptography and stumbled upon the following question to practice the knowledge about Congruence, Groups etc.

"List all Elements $x$, where $x^2 = 2$ in $\mathbb{Z}_{31}$

Okay, so the naive approach would be to iterate the group, multiply the element with itself and check if its residue modulo $31$ would be $2$.

So we are searching for every element which has a quadratic residue of $2$ in $\mathbb{Z}_{31}$.

Is there any "pen and paper" solution to do this, without having to iterate every element? Is there a theorem which could be used here?


texts: PRP vs PRF for the F-function of a Feistel network

texts: A Feistel network is generally defined with a PRF for its F-function, but PRPs have been used as well. What are the theoretical cryptographic implications of using a PRP instead of a PRF? Does it impact Luby and Rackoff's observation regarding 3 and 4-round Feistel networks with ideal F-functions?


texts: Is there any benefit to using a randomly chosen replacement strategy on a string before or after encrypting it?

texts:
This is more of a mental exercise for me than anything else. I've thought about doing something like this before, mostly to make a broken cipher a little more difficult to decrypt to plain text. I've simplified the strategy below, but in theory, you could use any length of replacement key first.

First, I would randomly choose a number of known length (say 4 digits). Let's use 1976 as an example. Then, I take the plain-text string, and do the following:

convert the string into a byte array.
for the first byte, i add 1. for the second byte, i subtract 9. for the third byte, i add 7, and for the fourth byte, i subtract 6. I repeat this throughout the byte array, then rebuild the string from the byte array. Next, I concatenate the 1976 key to the front of the string. Once that is done, I use standard AES 256 encryption.

Now, in practice, I would use more than just adding and subtracting and a longer integer value, but that gives an example of the "randomization" of the string prior to encryption. The idea is to provide an extra layer of randomness to the encryption scheme. However, I'm not sure if this provides any real value as if the IV/Key has already been obtained then how hard is it really to figure out what I'm doing with the appended integer? Would it be better to use this post-encryption? I'm really curious what the community thinks of this idea. Does it have any merits? What are the drawbacks? How good/bad of an idea is it really?


texts: How do I convert an elliptic key signature r and s value into a signature byte array?

texts:
I have an existing system that signs an arbitrary binary blob with an ECDSA key. The output of this is an r and s value. I now need to verify this signature on another system. On this other system though we are using BouncyCastle, and would prefer to just use the byte array verify method.

Unfortunately my cryptographic mathematical skills are not up to parr and I don't know how to convert my r and s values into a byte array for the signature. How do I do this conversion?


texts: Bleichenbacher attack, binary search, formula for $s_i$

texts:
Reading an excellent article explaining Bleichenbacher attack I came across the following statements under the formula for $s_i$:

  if we pick $r ≥ 2(bs_{i-1} - 2B) / n$, we obtain

  $(2B + 2(bs_{i-1} - 2B)) / b = 2s_{i-1} ≤ s_i$

Can anyone explain to me how the previous equality is obtained? If we try to reproduce it, we'll obviously get:

$(2B + 2bs_{i-1} - 4B)/b=(2bs_{i-1} - 2B)/b=2s_{i-1} - 2B/b$

Why the authors conclude that the result behind is equal $2s_{i-1}$? Moreover, in the code later they use

r = ceil((b*si - B2)*2,n) # starting value for r

as a starting point for $r$...


texts: How to find common answers without revealing differences?

texts:
Say Bob and Alice are trying to figure out the fruits they like, but don't want to reveal the fruits they dislike. How could they compare their list of liked fruits and reveal only the common set to the other person?
In this scenario, each party knows the full list of possible fruits to pick from. (It's shared information.) But if one person likes a fruit and the other doesn't, the person who doesn't like the fruit shouldn't know that the other does like it. There can't be a third party involved, so this operation needs to happen without sharing information outside of these two people.
Example fruit set: [apple, banana, grape]. (1 indicates interest, 0 indicates disinterest.)
Bob's selection: [1, 1, 0].
Alice's selection: [0, 1, 0].
In this case, how can Bob and Alice figure out that the shared answer set is [0, 1, 0]?
Bob doesn't want to share that he likes apples, because it wasn't a shared interest. (An odd scenario, but it works for the sake of this example...) And from Alice's perspective, she doesn't know anything about Bob's preference for apples or grapes, because she indicated that she doesn't like those. Similarly, Bob doesn't know anything about Alice's preference for grapes, because he indicated that he's not interested in grapes.
Because they don't want to share their preferences with a third party, they want to find a way to find the common set themselves without revealing disinterest. Is this possible?
I'm not well versed in cryptography, but it seems like private set intersection may be what I'm looking for? Is this the right direction?


texts: Is it safe to initialize secret keys by just reading /dev/random on Linux?

texts: For a software, I don't want the user to choose weak keys, so I plan to just read the needed number of bytes from /dev/random to create the needed secret keys. Is it safe to do so?


texts: How is an IV used in a Merkle-Damgard construction- Explicit example

texts:
I am interested to know how an IV is used in this simple Merkle-Damgard construction. I am referring to this image from the associated Wikipedia page as I explain further.

For the purpose of explanation, lets assume the following:

-We have a simple function: f(takes in 8 bits)= outputs 4 bits, or any similar simple function.(ex. f(a,b)= (a x a + b x b + 11) mod 15, where a,b are 4-bits)

-We have a 2 block message: M=101011110.

-The initial IV = 1111 or a similar simple IV

To my understanding, the first 8-bit block is 'a=1010 b=1111' and it would go through the function f(). I am unsure of how the IV would fit in to the process at this point, and how the IV would take action for the second block and so on. Any help is appreciated, and perhaps it may be the case that generalized variables as opposed to my specific numbers would make this example easier to explain in an answer.


texts: Replay attack prevention under strict conditions

texts:
Say I have a request-response protocol and the task to make it immune to replay attacks. The requirements are as follows:

The defense mechanism cannot rely on the clocks of the parties.
The defense mechanism should work even when requests are not sequential.
No party can store more than 1KB of data at any given time for the purposes of replay attack prevention (per session - see below).
No requests must be sent for the purposes of replay attack prevention.

Given that:

Before the defense mechanism is used, another protocol is used to authenticate the first party and create a session. The session ID is included in every request of the above protocol.
During the authentication protocol, up to 1KB of data can be sent to the first party for the purpose of replay attack prevention on the above protocol.

In what way does HTTPS handle replay attack prevention? How can this (the first described) protocol be made immune to replay attacks?

Considered Idea #1:

A 256-bit secret is shared by the two parties during the authentication protocol.
When party 1 makes a request, they include this secret in their message.
Party 2 checks that this is the same value they have stored. If so, it is included in the response and this value is hashed and stored, replacing the previous value.
Should the response be valid and contain the value sent, party 1 hashes the value sent and stores it, replacing the previous value.
Steps 2-4 are repeated for every request and response.

The problem with this is that requests need to be sequential.

Considered Idea #2:

Every time party 1 makes a request, a nonce is included.
Party 2 checks if this nonce has been used before with this session id, if yes, it denies the request, if not, this value is stored. Party 2 includes this nonce in the response.
Party 1 checks if the sent nonce is included in the response.

The problem with this is the large storage space needed.


texts: Is SHA-256 OK to use for key derivation for a key that is never persisted?

texts: The scenario: On the one side a user enters a pass phrase to encrypt a stream of data (AES-GCM) and a symmetric encryption key is derived from the pass phrase using plain SHA-256 (so not a slow function). Data is sent using TLS. On the other side another user has to enter the same pass phrase to derive the same key for decryption. If the key is never persisted, does it matter that a fast key derivation function is used?


texts:
According to the attached reference, does it mean that the adversary computes $PPT(initial~input)$, $PPT(z)$ and $PPT(f_i(x',y'))$?

For example, suppose the corrupted party, in the malicious model, has inputs $x,z$ and it wants to compute $x \land y$, then the adversary's output will be:

$PPT(x)$, $PPT(z)$ and $PPT(x \land y))$. Am I right?

Note: PPT is a probabilistic polynomial-time algorithm


texts: What is meant by the duality and homomorphism of an encryption algorithm?

texts: I am new to the field of cryptography and security so spare me with this question. What is the general idea of duality and homomorphism of an encryption algorithm? And how one may prove those two properties of a real-world encryption algorithm (e.g:- say for RSA encryption).


texts: Verification of Pinocchio (verifiable computation)

texts: I am reading the Pinocchio paper. The calculated result $y$ is a part of the verification input, but it seems to me, the verification procedure does not utilize the result $y$. Can anyone can help me to understand this?


texts: Secure symmetric encryption algorithm for any-size base62 data

texts:
I am searching for a secure algorithm to encrypt base62 (or any other base) data for ids in urls.

It should feature:

No blocksize etc, limiting the length of the message to a factor of n
If you have the decryted and the encrypted message you should not be able to guess the key
An avalanche effect
Any size of charset, not only 256 like in AES, DES etc.
High performance on modern CPUs

This is not required:

Streaming, it is only for small data

Is this possible?


texts: What is the probability of a collision in SHA-512 when the input is 512 bits of data

texts:
Although this question is strongly related to my previous question, it's certainly not the same:

Suppose the input of SHA-512 is 512 bits of data (so exactly the same size as the output). If I would test every possible permutation (so $2^{512}$ calculations), then will the output also be exactly $2^{512}$ different hashes, or will collisions occur ?

If collisions occur, would the amount of collisions and the 'size' of the collisions (approximately) be the same as statistics would predict after randomly generating $2^{512}$ 512-bit strings ? (With 'size' i mean the amount of times a specific hash occurs)


texts: How to decrypt RSA if ciphertext is less than the modulus and e=3?

texts:
I'm given a public key. Using openssl rsa ..... I got the public key has the exponent as 3. When I calculated the size of the ciphertext, it is 8 bits smaller than the 2048-bit modulus.

How can I decrypt RSA provided I only have public key and ciphertext?

Let me know if you want the files.


texts:
What is the name of an algorithm that hashes its result as an embed of larger set of data that results back to the hash?

For instance where $f(x)$ is the hashed result and $x$ is the dataset, and $f(x)=foobar, \\
x={\dots foobar \dots}$

Differently stated: I'm interested in a hashing algorithm that generates a hash code of a dataset with the actual hash value as a subset of the dataset. (If the algorithm doesn't exist, I propose it be named to the GEB hash.)

Maybe a "hands-on" application would help: A barcode embedded in raster graphic.  The barcode signifies the value of the hash code but the hash of the graphic as a whole (barcode too) renders the result value of the barcode.

A more abstract approach is embedding as a pre- or post-output sort of header in the same encoding...

My interest is in ensuring data completeness or cripple else.  No rogue data here--just can't cut off the hash off the end.  In above f(x) example, the dataset would/could be of the abstracted form $$x= {.... oo..b....fa...r}$$  It's interesting in the balance between having a algorithm that's substantive enough in influence/design of the 'original' and yet is not namely obtrusive.  In the world of say books, I would imagine "parity" bits contributing the hash hidden on the edge fonts, sans stenography meets authentication and validation.

In principal, the "hash sentence" in the book would be hashed itself to monitor data tampering in an insulated environment. ie. can't readily look up the hash code from another "verified source" but I can recognize the "thumbs up" image and so can my "compiler".


texts: Is there a signature scheme which doesn't rely on the difficulty of factoring/dlp which generates short signatures?

texts:
The Lamport signature scheme, for example, doesn't rely on the difficulty of any problem and it only depends on the existence of one-way functions.
Is there an alternative scheme which also doesn't rely on the difficulty of factoring/discrete logarithm, but provides shorter signatures?


texts: how calculate plaintext file size from length of encrypted one without decrypting

texts:
Silly question – is it possible to find out size of original file from encrypted file?  Encrypted with aes-128-cbc.
Looks like there is no way to calculate it. As far as I understand ,all original files with length between let’s say 33 and 47 will have length 48 bytes after aes-128-cbc encryption (should be rounded to next 16 byte block). But, just in case asking the crowd
Update:
Well, I’m not mathematician, just a programmer, and the formula provided in an answer below means not much for me ☹ so I need more plain explanation how I could that.
The story is - I encrypt files (longer than 48 bytes ) by using standard Node.js module (crypto). I ask this module to use aes-128-cbs algorithm (but, generally speaking, I could use others algorithms) and I know the key, the key length, the IV. Looks like I need to read last 2 blocks (32 bytes) of a encrypted file, give them to decipher, it will not be able to correctly decrypt penultimate block due to luck of IV, but should decrypt very last one.
What I suppose to do with this data (last decrypted block)? How EXACTLY I can calculate size of original file knowing content of last block, the key, the key length etc?
Thanks a lot in advance.


texts:
In lattice based cryptography, we say the average-case SIS (short integer solution) problem because it is such kind problem
                     " $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, finds a vector $s\in \mathbb{Z}^{m}_{q} \backslash \{0\}$ such that $As=0$ and $||s||\leq \beta$"

but not  instances like this
       " $A \stackrel{\$}{\leftarrow} \mathbb{Z}^{n\times m}_{q}$, finds a matirx $B\in \mathbb{Z}^{m\times k}_{q} \backslash \{0\}$ such that $AB=C$ and $||B||\leq \beta$".
The latter instances are more general and the former instances just include some cases of the latter.

And the same case happens in BDD (bounded-distance decoding) problem.  We say that LWE problem is an average-case problem because it just includes some cases of BDD problem.

Did I understand that correctly?


texts: Verification of signed message with encryption

texts:
I have a question about the message that is being encrypted and signed. Say, two users called Tom and Mary, both have a pair of private key and public key. Tom sends a message through a system that will encrypt and sign the message. 2 kinds of message will be sent
1. encrypted message  and,
2. hash function of the message, public key of Tom and Mary,  secret Key (which is chosen by Tom)

I would like to ask after Mary got the message, she could recover the message by the public key of tom. but how could she recover the hash function so that she could make sure this 2 kinds of message are signed by Tom?

Thanks!


texts: Can anyone briefly explain the 'theta step' of compression box in SHA3?

texts:
Can you explain the 'theta' step of the compression box:

D[X] = C[X-1] ^ ROT(C[X+1, 1])

In this step all the indices should be taken modulo 5.

Do we have have to rotate it after taking mod 5? And is C[X-1] left rotate or just putting the values of x as 0,1,2,3,4 and then taking mod 5?

And ROTC[X+1,1] is right circular rotation by 1 bit after taking mod 5, right?

Please help me regarding this.


texts: RSA signature attack check on lowest 16 bytes - Implementation

texts:
I am referring to solution given in this question

I need help to implement Poncho hint in this comment:

As the first question i have an RSA signature of 1024 bit applied on an hash (MD5) of the message.

I am trying to get a valid result coding it in Java but i don't get any result from my iterations.

Can someone help me to find out why i don't get results as mentioned by @Poncho?

Example of hash: 0xCC844F9AF903BCB3CB0A7F0433AF70D3
Decimal representation: 271849508914011436342484527734062018771

Thanks a lot.


texts: OTP same message encrypted twice (with different keys)

texts:
Lets say we have a message $m$ that we encrypt with two keys $k_1, k_2$ such that $k_1 \ne k_2$. This will produce two ciphertexts $c_1, c_2$ such that $c_1 = m \oplus k_1, c_2 = m \oplus k_2$.

The attacker managed to get the two ciphertexts and also has the knowledge that both ciphertexts $c_1, c_2$ represent the same message. Does this knowledge lower the OTP security in any way?


texts: In NTRU, if $N$ is not prime, prove that one can recover the private key by solving a lattice problem in dimension lower than $2N$

texts:
In the NTRU cryptosystem, it is suggested to take $N$ prime.
I want to understand why.

In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (as exercise) to suppose that $N$ is even, to consider the natural map
$$\mathbb{Z}[X]/\langle X^N-1 \rangle \longrightarrow \mathbb{Z}[X]/\langle X^{N/2}-1 \rangle,$$
and prove that one can recover the private key by solving a lattice problem in dimension $N$, rather than in dimension $2N$.

Can someone explain how can we do this, please?
Thanks in advance.


texts: Comparable or partially homomorphic public key derivation for signatures?

texts:
Are there any public key signature schemes that can be compared blindly or partially homomorphically based on the private key without knowing the private key?

Example: let's say I derive a public key from a private key via a secret seed "haha this is a secret 1001" I then derive another public key from another secret seed "haha this is a secret 1002". I then want to be able to compare the public keys lexicographically without knowing these seeds.

Being able to compare the signatures would also work, but only if they can somehow be compared on the basis of the seed used to create the key pair and not on the basis of what is signed.

A little bit of a weird question, but my intuition says this might exist.

Edit:

I thought of one solution but it's not very efficient. You could mandate a mapping from sortable secret keys to integers from say 0 to 2^32-1 (32 bits). Then you could just brute force search by hashing the secret keys until a public key is found whose least significant bits correspond to the ordinal. You'd then store the number of hashes required alongside the public key and compare on the public key's least significant N bits.

A more efficient way would be preferable of course.

Edit #2:

A description of the real world application might be helpful.

I want to be able to secure a distributed decentralized database against naive sorts of denial of service attacks and collision attacks.

It's a system that maps plain text keys to plain text values but uses a hash of the key to encrypt the value and then indexes entries by a hash of the key. This means the plain text key is hidden and the value is unreadable to anyone who doesn't know what key they're looking for. (This is itself not an uncommon technique in e.g. shared deduplicating storage systems.)

BUT... even if someone doesn't know the key they could add bogus entries with what looks like the same key (its hash) and nonsense values. This would pollute the cache with junk, waste space and bandwidth, etc.

So I have this idea. Take the plain text key, hash it, use part of the hash to encrypt the value, and then use another part of the hash to derive a key pair. Then sign the entry with that key pair. Use the public key from this pair as the encrypted key in the key/value store.

This means that you cannot create valid entries for a given plain text key unless you know that key, but you can prove that you know a key without revealing it.

The sortability desire comes from a desire to support ordered iteration queries in this cache. So I want people who know a given plain text key to be able to ask for it and all the keys greater than it or all the keys between two values. This is basically blind/homomorphic querying but with this weird twist as described above.


texts: Whether hash function of two values $h(a,b)=h(b,a)$ are same?

texts:
If two messages $M_1$ and $M_2$ are given as input to a hash function $h$ is it then true that $h(M_1,M_2) = h(M_2,M_1)$?

I have two messages. I want to know,

Is it possible to apply a hash function to two messages?
If it so is $h(M_1,M_2)=h(M_2,M_1)$ ?


texts: Difference between decryption and deciphering?

texts: Is there a technical difference between decryption and deciphering?


texts: ChaCha20-Poly1305: Can my salt/pass for a KDF also be the nonce?

texts:
I have a PSK. I don't want to use it directly. I want to pass a "salt"/password into a KDF and get a new key for authenticated encryption with ChaCha20-Poly1305 .

I need to give the other side the nonce used.

I don't have enough space to fit all of this in a packet.

My plan was to generate a random nonce. But then thought...

Is it bad to use my pass/salt (16 bytes) as the nonce (12 bytes) as well? I could save the space of sending the nonce by just lopping 4 bytes off the salt.

I know all about the dangers of reusing a nonce. But I'm not sure it applies here because my "old PSK" is thrown into the KDF with the salt/pass so does it matter if that also makes up the nonce?


texts: How can I decode a substitution cipher in the form of pictures?

texts: I'm very new to cryptography (and cryptanalysis), and I'm wondering how to decode a substitution cipher, where all of the letters are replaced with symbols, that is, pictogram cipher?


texts: What standards of ECC point compression exist?

texts:
The method that I used before to decode EC point from public key led me in a dead end. So I just want to know what yet I could try.
I've got a public key that I don't know how to decode and I am looking for a list of commonly-used encoding/compression schemes.
Here, a part of the test certificate with EC curve parameters (polinomial representation F2m):


texts: Possible deciphering methods for the steganography on an old check?

texts:
This check was deposited in the 1930s, and it was issued by OCBL (an old bank in Singapore). The checks issued by this bank had an interesting feature - an obfuscated pattern printed on the back of the check.

All original documents about the design of this check have certainly been lost, and there isn't any later documentation that addresses the usage of this "pattern", but some agree that it might be an example of steganography, so that security personnel could put a cardon-grid-like card on the top of the pattern and thus reveal some information to help verify the check's authenticity.

My question is not about deciphering the secret based on what it has to offer as steganography, but focuses on the following directions:

Is this pattern really an example of steganography? Has any bank or financial institution ever printed a similar type of pattern on their checks before? If so, what is it?
If it is steganography, what information could be concealed in it? As far as I know, many checks of this type share the EXACT same pattern on the back. Different patterns can be seen on other checks and bills.
If it is steganography, are we able to decipher the message from the pattern? What possible methods or reverse-engineering technology could be used to detect the methods of concealment, provided that such steganography is not uniquely deployed in this case?


texts: Use of elapsed execution time as a variable input

texts:
Given that, with a significant number of decimals, it may be difficult to predict elapsed execution time of a piece of code, despite having knowledge of exact hardware and software specifications; is there any algorithm which uses the elapsed execution time of the encryption algorithm itself in order to feed mathematical complexity back into itself?

(I'm not suggesting this would be a good idea)


texts: Explanation of each of the parameters used in ECC

texts:
I'm having a very difficult time finding a clear explanation of the parameters used elliptic curve cryptography. I know for certain that $p$ is the number or order or whatever of the given field that a particular curve uses. I know that $k$ is what is used as the secret key and that $Q=(Q_x,Q_y)$ is the public key. But playing around on these two pages and seeing the contents of this file have left me more confused. What is the importance of $P$ and how does it differ from $Q$? Do $a$ and $b$ change depending on the key in question or are they held constant for a curve? What is the function of $n$? It always seems to be slightly less in value than $p$. How do $G$, the order of the curve, and the seed fit in?

Finally, how is a number encrypted? Is it done by multiplying $Q$? And how can I extract the coordinates of Q from its "compact" form used in certficates?


texts:
I'm trying to design an extension to Shamir's Secret Sharing that would allow the participant to specify a password instead of remembering/storing a large integer or binary data. So far, I have two ideas, both based on some PBKDF:

Run the password through a strong PBKDF to make $k_i$ then publish $(i, f(i)⊕ k_i)$ in a public, read-only location.
Similarly, run the password through a strong PBKDF and then publish $(i, \text{AES}(\text{key}=k_i, \text{message}=f(i))$ in a public, read-only location

I like the simplicity of the first method, and rationally I haven't found anything wrong with using nothing more than XOR, but to my intuition it smells a bit fishy.

Am I divulging any information that would weaken the algorithm by using just XOR? What about with AES?


texts:
Does there exist any cryptographic algorithm which encrypts data in such a way that it can only be decrypted after a certain period of time?

The only idea that I can think of, is something like this: Seed a PRNG with a public value. Run the PRNG for a week and use the final value it produces to encrypt the message. Now anyone who runs that PRNG for a week starting from the seed value you made public can decrypt the message. Obviously this breaks down since they could use more computational power than you; if the time span was years then Moore's Law would apply, etc.

Is there anything like this other than physically burying a private key on a USB stick in a literal time capsule?


texts: Why is CAMELLIA suddenly so widely used?

texts:
When nowadays I point my browser to https sites, the cipher that is on most occasions used is Camellia. My browsers (Chrome and Firefox) seem to prefer it, even when AES is available.

Is that not kind of dangerous? Camellia did not receive so much scrutiny as did e.g. AES, so we know actually less about its security. Would it not be much better if AES was the default? I know I can change the cipher on Firefox, but it is not obvious how to do the same in Chrome.


texts:
In their work on SHA-1 collisions (cf. the EUROCRYPT-2016 paper “Freestart collision on full SHA-1” by Stevens, Karpman, and Peyrin) Stevens et al show that they are able to generate "freestart collisions" on SHA-1. They say:

  Even though freestart collisions do not directly lead to actual collisions for SHA-1, in our case, the experimental data we obtained in the process enable significantly more accurate projections on the real-world cost of actual collisions for SHA-1, compared to previous projections.

What is a "freestart collision" on a hash function?


texts: GCM mode of operation with long-term keys

texts:
Regarding GCM, NIST specifies the following:

  The total number of invocations of the authenticated encryption function shall not exceed $2^{32}$, including all IV lengths and all instances of the authenticated encryption function with the given key.

In another thread on this forum, @Lery suggests deriving session keys from the long-term key using a key-derivation function (KDF) by computing $k_s = \mathrm{KDF}(k,r)$. Here, $k$ is the long-term key, and $r$ is a random nonce generated per GCM usage. $k_s$ is the key used for GCM.

This makes sense from a security standpoint, but to increase performance, I'd like to investigate whether computing the session key as $k_s = k \oplus r$ poses any threat to the security of GCM.

You can assume that the value of $r$ is appended to the ciphertext, but is not encrypted. So, anyone seeing the ciphertext can easily deduce the value of $r$.

The adversary is said to attack this scheme if he can break the properties often associated with authenticated encrypted: IND-CCA security, or unforgeability.


texts: How to handle entropy and CTR DRBG for TLS on embedded system?

texts:
I am trying to use mbedTLS on a STM32-Nucleo microcontroller (STM32F746).

The TLS library wants a RNG function (naturaly), the STM32 has a hardware RNG verified according to NIST SP 800-22.

The hardware RNG only outputs unsigned 32 bit integers each call, but several calls could provide 28, 32 and 255 byte random arrays needed by TLS.

Now, can/should I use this RNG function to generate random numbers directly for TLS or should I use this Hardware-RNG as Entropy for mbedTLS CTR-DRBG function?


texts: What are best known attacks for finding partial target pre-image?

texts:
Just a follow up on this question since I don't have enough point to comment:
Does a partial preimage attack imply a preimage attack?

Partial target preimage attack: Given $M$ and t-bit partial target of $d \leftarrow H(M)$, find $M^*$ such that t-bit of $d^* \leftarrow H(M^*)$ is the same as the t-bit of $d$ at the same position.

My question is what best known attacks are.


texts: Determining the algorithm used to generate a digital signature

texts:
I have a string "abcd pqrs". This string is digitally signed with an X.509 certificate (with its private key) and it produces a signature.

From the signed string, is it possible to find out what hashing algorithm was used?

Also, does the signed data always contain the certificate or the public key used to sign the data? If it does, how can I extract the certificate from the signed data?

The only information I have is that it's signed by an X.509 certificate.

This is the problem I am trying to solve:

I have an opaque tool which takes an X.509 certificate, the corresponding private key and "data to be signed", and gives me signed data. I have no information about what kind of hashing/signing algorithm it uses, I have no information about whether it produces a detached or attached output.

Basically, I want to verify the signature and the data — but before I do that, I need to have some info about it. I have access to original unsigned data.


texts:
I am having problems in doing pairing in cryptography. I have tried the PBC library but seems like it doesn't work and I do not understand the documentation because it uses C++ language.

Is there a library for pairing in cryptography using PHP language?

or is there anyone who can explain how pairing works in cryptography with an input and output?
For example: Weil Pairing or Tate Pairing which uses Miller Algorithm.

Thank You


texts: Cryptographic enforcement schemes using Diffie-Hellman

texts:
If one wants to set up a decentralized cryptographic enforcement scheme in which the level of 'confidentiality' of information is marked by its position in a poset, why not use Diffie-Hellman to derive the key of a node from its immediate parents?

This is as opposed to the tree-based scheme described in this paper.

In more detail:

You have a poset $X$ from which you want to build a CES. You have a public one-way function $f$. The poset has a top element $r$ and a randomly generated key $k(r)$. Here is how you derive $k(x)$ for all $x \in X$: Let $u \in X$. We can assume one of only two possibilities (we can easily generalize to more than these):

$u$ has one parent $x$. Then $k(u) = f(k(x))$.
$u$ has two parents $x_1$ and $x_2$. Then choose a random DDH-hard
cyclic group $G$ and a generator $g \in G$ and publish $(G, g,
   g^{k(x_1)}, g^{k(x_2)})$. $k(u) = g^{k(x_1)k(x_2)}$.

[edit]

When sending a message, a chain can be used to communicate its position in the poset. Let's say that if a node $u$ has one parent, its 'name' will be denoted $u$ (which will be random). Let's say if it has 2 parents, its name will be the $(G, g, g^{k(x_1)}, g^{k(x_2)})$. Then you publish the chain.


texts: Unable to implement Client and Server Side Hashing (Validation problem)

texts:
I'm trying to implement hashing on both client and server Sides for my web/mobile Application.

On the client side, I implemented the slow hashing algorithm (bcrypt)
On the server side, I tried to use a fast hashing algorithm (MD5)

Here's what I did:

The user enters the password in my app.
The password is hashed on the client side using bcrypt (slow hashing algorithm).
The password hash travels via SSL to the server.
On the server side I use MD5 (fast hashing algorithm).

The problem here is: on the client side, as I mentioned already, I'm using bcrypt (with a random salt). So, every time the resulting hash is a different one.

Further hashing the resulting hash from the client ends up with a different one on the server side, since MD5 (without salt) produces a different server hash for different client hash.

So users are not able to log in.

How can I solve my problem? Which algorithm would be better suited for my problem here?


texts: How can I use SSL/TLS with Perfect Forward Secrecy?

texts:
I'm new to the field of cryptography, but I want to make the web a better web by setting up the sites that I host with Perfect Forward Secrecy.  I have a list of questions regarding the setup of Perfect Forward Secrecy.  Here it goes:

Can my choice of certificate authority hinder the use of Perfect Forward Secrecy?
How can I create the strongest certificate using ONLY Perfect Forward Secrecy (meaning if the browser can't use PFS, it won't load anything)?
Are there any extra settings that I need to know about for configuring my sites to use these certificates (especially since I only want PFS)?
Anything else that I should know, feel free to tell me.  I'm completely new to this idea.


texts:
Alice has two secret numbers, a and b. She publishes c1=E(a), c2=E(b) and c3=E(a+b). Is there an encryption system E such that anyone would be able to prove that the c3 as published by Alice is actually E(a+b)?

EDIT: Modified the question to use "anyone" instead of "Bob".

Note that this is different from homomorphic encryption. In case of homomorphic encryption Bob is able to compute E(a+b) himself, but he is not necessarily able to prove that E(a+b) as computed by Alice is correct. What's needed here is a system where Bob is not necessarily able to compute E(a+b) but is able to prove Alice's result.


texts: How to solve rubix-cube like symmetric encryption

texts:
So for a project at University I wrote a symmetric encryption system that was very similar to how a rubix cube would work. I had each byte of my data mapped to a element in a grid, with 6 grids in total (forming a cube), and the grids had a relationship where you could apply a swap function to each row/column and it would swap the same 4 lines in the grids on the same direction. It could encrypt up to 4 mb of data (64 x 64 grid)  at a time and used the set of moves used  in the process as the key (face 1 line 27 swap left etc.)

The catch with the system was that I haven't solved a rubix cube myleself... ever. So I managed to create a jumbled mess of my initial data and when I tried to decipher it (doing the opposite direction swap, from last swap to the first) It would remain a jumbled mess.

Due to a busted hard drive I can't show you the code I wrote for it anymore (it was in java) but I intended to try and recreate the project in my spare time And I would like to see what I could do to prevent creating a data shredder again.

Help would be greatly appreciated, I will provide additional clarifications if necessary.

EDIT: The question was Is this the correct way to solve a rubix cube (reversing the moves)? and if not what would the correct way be?

The system had more stages to it beyond this transposition stage but they were not made by and therefore worked fine :)


texts:
As indicated at

Key generation for AES-GCM-256 file encryption

I'm currently working on a file encryption software. In the above thread it was suggested that, for performance reasons, I use a combination of scrypt and HKDF.

But how should I go about using HKDF to derive a new key for each file? As suggested in the above thread, I intend to produce a single master key via scrypt and from that I want to derive file encryption keys via HKDF.

So far I have come up with two possible ways of doing this:

(1) Run HKDF (extract-then-expand) with the scrypt result as input key material (ikm) and a NEW random salt for each file to be encrypted

(2) Run HKDF (extract-then-expand) with the scrypt result as ikm, a FIXED random salt, and a random 'info' value for each file to be encrypted

Which - if any of these - is the better or correct way of doing what I want? As I understand it, NIST Special Publication 800-56C, explicitly dsicourages re-using the same ikm and just varying the salt. But I don't exactly understand why and their use case (shared secret Z as ikm) is different from mine.


texts: Can zkSNARK or other zero-knowledge proofs be used to proof message authenticity without revealing private key?

texts:
The situation:

Alice and Bob are exchanging messages encrypted by some known asymmetric encryption protocol. All their encrypted messages, as well as public keys are intercepted by Charlie.

Can Alice reveal decrypted messages to Charlie and provide him a zero-knowledge proof (for example zkSNARK) that deciphered text of the messages are indeed decrypted messages which he intercepted?

Can she do it without revealing her private key?

If so, can this method be used in any asymmetric cryptographic protocol without any special modifications to that protocol?

What about symmetric encryption, and passphrase revealing?


texts: Is there a generic attack on encrypted CRC32 when used as a MAC?

texts:
I am examining a protocol that uses CRC32 as a MAC (see note 1) the weaknesses of this method but I would nevertheless like to see if it is just weak or actually relatively easily to break.

The examined protocol has the format more or less of:

Plaintext = Headers (6 bytes) || CRC (4 bytes) || Data
Ciphertext = 3DES-CBC(Plaintext)

This is used for a Server to send a Client a message and the Client will authenticate the message by decrypting it and checking the CRC. An attacker cannot ask the Server or the Client to encrypt a message, they could predict though the plaintext from a ciphertext.

Searching about it I can see that there is an attack on SSH 1.5 that is similar. To perform the attack the format of the data is put into this format for SSH:

Plaintext = Padding (8 bytes) || Data || CRC (4 bytes)
Ciphertext = 3DES-CBC(Plaintext)

The attack is performed partially by taking advantage of the CBC encryption by changing the first block which is the 8 byte padding in order to manipulate the second 8 byte block. If I was to perform the same attack though on the examined protocol since the 4 byte CRC is split between the first and second protocol it wouldn't work.

Note that the question is not if the protocol is weaker compared to a protocol where a proper MAC like HMAC had been used but if there is any attack that could relatively easily break the authentication.

NOTES

From fgrieu: The terminology is not quite right: CRC32 can't be used as (a weak substitute for) a MAC, for it is a keyless transformation of the message. Rather, here, it is used as (a weak substitute for) a hash in a hash-then-encrypt scheme


texts:
We obtained $l$ vectors $B_i$ of $c$ bits $b_{i,j}$. These are an altered form of vectors $A_i$ where the last $n$ bits of each $A_i$ are an affine function of the other bits of that $A_i$.

We want an efficient algorithm yielding a maximal subset of vectors $B_i$ such that the last $n$ bits of each $B_i$ in the subset are an affine function of the other bits of that $B_i$.

By affine function, we mean there exist constant $K$ and $c-n$ constants $K_j$, each $n$-bit, such that for each $i\in[0,l($, the last $n$ bits of $A_i$ are $K\oplus\left(\displaystyle\bigoplus_{j\in[0,c-n(}a_{i,j}\,K_j\right)$.

$n\ll c\ll l$, and $n$ is known. The alterations have been caused by random communication errors (independent as a first order approximation), and are few enough that $B_i=A_i$ in most cases.

One application is cryptanalysis of an hypothetical affine $n$-bit MAC defined by unknown keys $K$ and $K_j$ (as there) with alteration in the available data. If the algorithm scaled well for large error rate, I could imagine application to the cryptanalysis of weak cryptosystems with some degree of linearity.


texts: Is there a system where I can securely store a secret value and compare a semi-ambiguous input to it?

texts:
I have an idea for a new kind of mobile phone lock screen. When you first create your pattern, you put together a series of colors and compass directions from the following choices: Red, Blue, Yellow, Green, North, South, East, and West. They can be referred to by their first letter. This pattern is the secret I wish to securely store.

Later, when you go to unlock the device the colors overlap the directions and every time you press on the screen you are providing ambiguous information: a color and a direction. After each press, the colors randomize to new locations on the compass. You only mean one piece of information or the other, but it's ambiguous to any Eve that might be observing you. It's also ambiguous to the device itself. The problem I'm trying to solve is how can I compare the series of inputs against the secret and determine if it's a match where the secret is securely (ideally irreversibly) stored?

For example, the pattern might be North, Red, West, Green, and North. I would securely store NRWGN. When the user goes to unlock their screen, they could press a combination similar to North and Red, West and Red, West and Blue, South and Green, and finally North and Yellow. With each press I only need half of the information that's provided and the other half can be ignored. But at the time of input, I can't tell which piece of info is the important half. Hashing every possible combination of colors and directions quickly grows too unwieldy and insecure. At the time of input, I don't even know the length of the secret. If I really need to, I suppose I could store it, but I don't like that.

Here's a functioning jsfiddle prototype, the same one that's on my blog at the link above. It works by keeping a record of the unencrypted pattern and comparing press by press against that pattern. If either piece of information is correct it is accepted and the process moves on. It behaves the way I would like but it does so insecurely.


texts: Why does SHA-1 algorithm have exactly 80 rounds? Is it to reduce collisions? If yes, then why do SHA-2 and SHA-3 have a lower number of rounds?


texts: Why would you want to keep the Initialization Vectors Public?

texts:
So I was researching Initialization Vectors (IV) and even took a look at this thread... What is the main difference between a key, an IV and a nonce? ,but I was hoping that I could get some clarity.
Everyone keeps saying they IVs need to be public because the recipient of a cryptographic message will need to first decrypt the cipher text with the cryptographic key, and then the recipient must have the IV to derive the original plaintext message... so whats the point of having the IV public if its there to increase confidentiality.. like if a threat-actor has the key then they can grab the plaintext straight up..
Please let me know if I am completely off.


texts: Is this encryption algorithm built from MD5 secure?

texts:
I'm being asked to use an encryption algorithm in my code, and besides the fact that I'm sure there will be implementation faults that lead to vulnerabilities, I also have concerns about the algorithm itself. I'd like to know how strongly I need to convince these guys to not use this. If it is an acceptable algorithm and there is a name for it, I'd like to know so I can find an implementation of it somewhere (I've been trained to not implement my own crypto).

I'm not a cryptographer, and this is coming from a large company and from people with much more programming experience than I have, so if I do need to convince people not to use this, it will be difficult.

The algorithm starts with a secret concatenated with a random string the length of an MD5 digest.
It MD5-digests this initial string and XORs the digest with the input data (up to the length of the MD5 digest).
It takes the result of that XOR operation, saves it to the output buffer and digests it concatenated with the original secret to get a new digest.
Then it keeps going until it has covered the whole input.

The goal of this scheme is to allow messages to be read by parties who know a secret and to not allow those messages to be read by parties who don't know the secret.

Now that I understand the notation, I can make this clearer:

$C_1 = M_1 \oplus \operatorname{MD5}( secret || random )$

$C_n = M_n \oplus \operatorname{MD5}( secret || C_{n-1} )$

I also don't understand how this is to be decrypted. It seems like the same random string is needed for that, in which case, we have the problem of how to get the random string to the other parties – is it okay for that part to be sent in plaintext?


texts:
I've read a paper that says that one of the "assumptions" that it makes is secure broadcast. Why is this an assumption? Can't a broadcast channel be built with simple primitives--i.e. encrypt and sign messages with a shared key?

And, assuming that there is something more that I'm missing, how are broadcast channels usually approximated in practice?


texts: Ed25519 and hierarchical deterministic wallet

texts:
I'm building a solution based on the stellar codebase and using the Ed25519 curve for the signatures. One of the features I've been adding to the system is a support for hierarchical deterministic wallets according to BIP32. For that use case I've removed the clearing of the lowest 3 bits and setting the 254 bit for derived keys still having this features for regularly generated keys.

This allowed me to implement the HD part, but exposed the signature made by a derived key to the timing and the small-subgroup attacks. The derived keys are used as a single/couple time signers and does not participate in any DH communication.

This brings me to the question whether such schema can be considered secure?


texts:
I understand how RSA can be used for message encryption:

Alice wants to send a message to Bob.
Bob generates a public key $(n, e)$ and private key $d$; he keeps the private key for himself only, and sends the public key to Alice.
Alice encrypts the message with the public key.
Alice sends the encrypted message to Bob.
Bob can decrypt it with the private key.
Eve who stole the encrypted message (but who has not the private key) cannot decrypt it.

Can we describe a similar situation (in Layman's terms, with two people and a third malicious person) to explain how RSA can be used for message signature?

Note: My problem is not the maths (I studied RSA and understand the maths in it) but more an example of situation showing how signature works.


texts: Is AES in XTS mode insecure for data stream encryption?

texts: Can anybody explain to me why AES in XTS mode is supposedly insecure for data stream encryption? I have been unable to find a clear explanation for this.


texts:
I'm creating a program with key access for a determined term. I've made a code that will generate a key (password) with 16 characters length. The following information is encoded:

initial date 6 characters, ex. 010120;
term up to 3 characters length, ex. 1 or 10 or 365 days;
term length identificatior, ex. 1 or 2 or 3, depending on term number length;
6 randomly generated symbols: lower/uppercase letters and numbers.
These characters are scattered in the password string using some logic (to be decoded by password verification code).

Encoding is simply based on ASCII codes of symbols.

Example of coding letters: a b c d e f = ASCII codes 126 + 127 + 128 + 129 + 130 + 131 = 771 = 7 + 7 + 1 = 15. 15 is the control sum. Thus generating a key my code loops through random codes ASCII until the control sum will be equal 15 - this is the generated letter part of the password. This control sum is after used to verify is the password is correct. Digits for the date are encoded simply by adding a constant value to the ASCII number code (48 to 57) to get a letter.

Here are examples of keys (used another control sum):

3Y6CEecb0MYc1e1c, oPFjeefcAD8m2dmd, bF5bGfdb4dud2ejd, ClEigfdbydcd2ezd

My question is about the "strength" of this password: how easily it could be hacked, or date and term part discovered?


texts:
Let (S,V) be a secure MAC defined over $(K,M,T)$ where $M = \{0,1\}^n$ and $T =\{0,1\}^{128}$. Which of the following is a secure MAC:

$S'(k,m) = S(k,m)[0,\ldots,126]\quad and \quad V'(k,m,t) = \big[V(k,\ m,\ t\big\|0) \ \text{ or }\ V(k,\ m,\ t\big\|1)\ \big] $
$S'(k,m) = S(k,m)\quad and \quad V'(k,m,t) = \big[V(k,\ m,\ t) \text{ or } V(k,\ m \oplus 1^n,\ t)\big] $
$S'(k,\ m) = \big[ t \gets S(k,m),\ \text{output } (t,t)\ \big)\quad and \quad V'\big(k,m,(t_1,t_2)\big) = \begin{cases} V(k,m,t_1) & \text{if } t_1 = t_2 \\ \text{"0"} & \text{otherwise} \end{cases} $
$S'(k, m) = S(k, m \oplus 1^n)\quad and \quad V'(k, m, t) = V(k, m \oplus 1^n, t).$
$ S'(k,m) = S(k,\ \ m[0,\ldots,n-2] \big\| 0)\quad and \quad V'(k,m,t) = V(k,\ \ m[0,\ldots,n-2] \big\| 0,\ \ t) $
$ S'(k,m) = S(k,m \oplus m)\quad and \quad V'(k,m,t) = V(k,\ m \oplus m,\ t) $

The first one I think it's a secure MAC, but I don't now how to prove.

For the 5th one I think that it's not a secure MAC beacuse I can just ask for the tag of 0000...01 and I find out the tag for $0^n$, which is a valid one. So, it's not secure.

For the sixth, I can ask for $S'(k, 1^n)$ and I find out $S(k, 0^n)$, which is $S'(k, 0^n)$, so it's not a secure MAC.

Is my way of thinking correct? how about the others MACs?
thank you!


texts: How are Elliptic Curve Cryptography and Pairing Based Cryptography related?

texts:
I have been doing a project that uses the PBC library developed by Ben Lynn. But I am still not clear on how PBC is related to ECC.
I know that this is a site for complex crypto QA, but I did not know where else my question would be answered. I have tried to learn from online sites, but I don't understand most of them.

If my questions merits a good answer, please help me. Otherwise please give me some pointers in the right direction.


texts: Where can I find a description of the SHA-0 hash algorithm?

texts:
Where can I find the description and or pseudocode for the SHA-0 hash algorithm? I am looking for something on these lines: HMAC RIPEMD.

I have been implementing a few of those (HMAC, HOTP, TOTP and MD4, MD5, RIPEMD-128,160)


texts:
I've just made my own implementation of Diffie Hellman in nodejs (its for a project of mine). However the shared keys are integers, I want to use those integers as a key to encrypt data. This is an example output:

Publicly Shared Variables:

    Publicly Shared Prime:  9811

    Publicly Shared Base:   844

Private Variables:

    Alice Secret:   6

    Bob Secret:   15

Alice Sends Over Public Chanel:  905

Bob Sends Over Public Chanel:  1168

------------

Privately Calculated Shared Secret:

    Alice Shared Secret:  3793

    Bob Shared Secret:  3793

What would be the best encryption method, using the key of those integers. Sorry this is a bit hard to explain. Thanks alot!


texts: Matyas–Meyer–Oseas for super-fast single-block hash function

texts:
Is it basically safe and correct to use the Matyas–Meyer–Oseas construction to turn a fast block cipher like AES into a really fast single block hash function?

By single block hash function I mean one that hashes, say, 128 bits of input and produces 128 bits of output. I don't need variable or larger message sizes and if I did I'd use SHA-2, SHA-3, etc., but those are a lot slower for really short fixed length messages. Benchmarks show that this AES construction is more than 10X as fast for hashing single block length messages on a machine with AES-NI CPU extensions.

If I'm understanding Matyas–Meyer–Oseas, the hash function would consist of AES initialized with a static predefined key and then used to encrypt a single block of input ("ECB" mode). The result of encryption would then be XORed with the original block to produce an output hash. Further initialization of the cipher with subsequent blocks wouldn't be done since you're only hashing messages whose size is equal to the block size.

If you're curious the application would be Winternitz one-time signatures. Winternitz signatures involve a whole lot of iterative hashing of single block size messages. Preimage resistance is important so a good hash function is needed but for compact signatures you want to increase the height of the "columns" in the signature.


texts:
I am considering a situation where an adversary does not have access to the $n$-bit output string of a PRNG, but instead receives a noisy version of it, where each bit of the string is flipped with probability $p$. We assume that this noise which causes the bits to flip is truly random.

What can we say concretely about the difficulty of distinguishing this noisy PRNG output from a truly random string? Of course, for $p=0$ we recover the standard scenario for the PRNG and the problem is as hard as solving the underlying computational problem, and for $p=\frac12$ the string is truly random. But what about intermediate values of $p$? Does the distinguishing problem become significantly more difficult even if $p\ll 1$?


texts: Security properties and Cryptography objectives applied in algorithms

texts:
We all know there are five properties of Security. They are:

Confidentiality
Availability
Authorization
Integrity and
Provenance

As Security and Cryptography are co-related these properties also applicable to Cryptography as well (are't they?). I can understand how a Cryptographic algorithms (e.g. AES)  maintain these properties. But what I don't understand how does the last property "Provenance" is applicable to AES or DES/TripleDES ?

There also four objectives  of Cryptography. They are quite same as the Security properties except for "non-repudiation". How does AES or DES/TripleDES fulfils this objective?


texts:
For academic purposes, assuming $n, p, q$  with $n\approx 2^{4096}$ and $p,q\approx 2^{2048}$.

I need to find ($e,d$) such that:

$e$ is smaller than $2^{64}$
$d\approx 2^{4096}$ and will have as much zeros as possible in binary form.
($d=$10000...0001 will be the best obviously, but I'm not greedy)

What will be the best way to find such a pair?

($n,p$ and $q$ are not fixed, if there is a way to find such $e,d$ by changing them then it is also a valid solution, as long as their lengths are as stated)


texts:
I have a task to decrypt custom made transposition cipher, as I'm not the cryptography expert, I would appreciate any help.

I've been given the table of characters ...

M A N B C
D E F G H
I K L O P
Q R S T U
V W X Y Z

... with images representing:

swap
up twice
left twice

(There's no word about the order of these steps)

The hints are:

MAN
NP = CL

Texts to decode is: ET KO KF

I've tried to fit the steps for getting CL out of NP, but with no luck. Also, there's no sign if the characters are "pushed" while making steps, or the character we're moving is being swapped with the next letter (I'm not even sure if we're moving characters or columns or something else). I know it might seem not explained enough, but as I'm not an expert, I wanted to ask you as it might be some known pattern.


texts: How do I do a literature search of the research literature on cryptography?  Assume there's some topic in cryptography I'd like to learn more about; how do I search the cryptographic research literature to find research papers that might be relevant?  What's the best process to use for finding relevant research?


texts:
I was watching this class about AES in this LINK and I was trying to grasp the concept of prime fields, which is a finite field with prime order $p$.

The non-prime field part (order is $p^n$) is where it gets harder for me. The teacher jumps into "extension fields", and does not explain the link between it and non-prime fields. Also, he just affirms that elements of $GF(p)$ are integers, while elements of $GF(p^n)$ are polynomials.

Why the difference between the two?


texts:
I want to try to break an LCG generator just as programming practice task. I found similar issue at Cracking a linear congruential generator.

Assume that m is given. The answer to the link above assumes that there are 3 consecutive output values given. Then it is just solving the resulting 2 linear equations. But what if there are only 2 values given? For some values, there probably will be several candidate LCG. How to list all of them and do so efficiently?


texts: Question on the CPA-security proof of the CTR-Mode

texts:
While reading Katz & Lindell's textbook (2nd edition) I found a proof for the CPA-Security of CTR-Mode. It can be found at the end of chapter 3.6.2 (page 93 and 94). I don't quite understand, why the proof is that complex, so I got two basic questions about it:

Why is the extra Scheme (cryptosystem) based on a true random function instead of a PRF necessary?

Why do we want to proof it with CPA-security for multiple messages? As far as I know, CPA-security for single messages implies CPA-security for multiple messages and vice versa. Therefore that just makes is unneccesary complex.

Why can't the proof be done simpler? The sketch of my idea would be:

Suppose A is an adversary against the CTR Kryptosystem based on a secure PRF function

A runs the CPA-Experiment with two messages $m_0, m_1$ and recieves $(IV,c)$ from the challenger

A can use its encryption Oracle for a polynomial amount of time $p(n)$ and gets, for simplicity, $n$ duples $(IV_i,c_i)$. That leads to 2 cases: 1. An overlap occurs. Because A does not only succeeds, if $IV = IV_i$ but also if $IV+x = IV_i+y$ (for some $x,y \geq 0$, because of the counting factor of CTR-Mode). So this happens in $2p(n)^2/2^n$ instead of $p(n)/2^n$ (birthday paradox, because of $IV+x = IV_i+y$). As probability to win in that case is 1, but the probability for this case is negligible: $2p(n)^2/2^n \in negl(n)$ 2. There is no overlap and A probability to win is $1/2$, because the PRF is secure.

Combining these two cases the probability of A to win is $1/2 + negl(n)$, which means, that CTR is CPA secure.

Edit:
Thank you for the answer! They helped me a lot in understanding the topic. But this led to another question related to this:
My professor proofed CPA-security for Encryption #1 based on PRF via a reduction proof using contradiction. The basic idea:

Basic assumption PRF is secure

Assume an adversary A against #1

Use A to build a distinguisher D to solve the the basic Assumption (D plays the CPA-game with A and therefore can break PRF)

Contradiction leads to proof if CPA-security

Because the proof in the book is based on the proof of the CPA-secure PRF-encryption, it should be possible to construct a proof, based on the the proof of the CPA-secure PRF-encryption using contradiction, right?
I give it a try:
This leads me to the following: A solution using contradiction would be more intuitiv (and I could understand it). So now therefore I give it a try:

Basic Assumption: PRF is secure

Assume an adversary A breaking the the encryption. A is able to use an encrpytion orakle (because we want to proof CPA-security). Let a have a non negligible success probability.

Using A we an build a distinguisher D breaking the PRF: D gets function not knowing weather it is a PRF or a true random function f. D simulates the CPA game with A using PRF or f. This leads to two cases:

3.1 D got a PRF. D is using the PRF-encryption scheme. A can break it with non negligible probability and D outputs what A ouputs.
3.2 D got a true random function. Now it gets funny: D firstly has to construct a new encrpytion scheme. For that he uses the old and just uses f instead of PRF. But now A can't win the game with more than a negligible probability: A can make p(n) many encryptions getting. Now the same argument as above can be used for overlapping (Because A does not only succeeds, if $IV = IV_i$ but also if $IV+x = IV_i+y$ (for some $x,y \geq 0$, because of the counting factor of CTR-Mode). So this happens in $2p(n)^2/2^n$ instead of $p(n)/2^n$ (birthday paradox, because of $IV+x = IV_i+y$). As probability to win in that case is 1, but the probability for this case is negligible: $2p(n)^2/2^n \in negl(n)$)

Therefore D can succeed with more than non negligible probability distinguishing PRF and f, which breaks PRF and therefore leads to a contradiction

Now only ING-CPA-security for single messages was shown, but because ING-CPA-security for single messages implies ING-CPA-security for multiple messages, we also showed that.


texts: Real world performance of (still theoretical) Grover's Algorithm

texts:
Grover's Algorithm is a quantum algorithm for searching "black box" functions and could be used to reduce the search space for things like symmetric ciphers and hashes by as much as half (quadratic speedup). This would effectively reduce e.g. SHA-256 to 128 bits or AES-128 to 64 bits.

... in theory, of course. Nobody's built a QC that can run Grover's Algorithm yet and I doubt one will exist that can do it for anything other than toy problems for quite a while.

That being said I have a question about how Grover's algorithm works.

My understanding is that in Grover's algorithm there is a classical step in which the classical function must be evaluated for a given point to test if that point is the correct answer.

If that's the case, could you practically limit the performance of a post-quantum search by designing an intentionally expensive and inefficient algorithm? I'm thinking of some of the memory-hard compound hash monstrosities like CryptoNight that are used in the cryptocurrency world as block hash / mining functions. Would a slow complicated memory-hard algorithm effectively limit the performance of Grover's algorithm in the real world by making each iteration terribly slow? So even if you get quadratic speedup, 2^64 or 2^128 searches of something that takes 250ms of classical compute time per search would still take an absurd amount of time.

Thoughts?


texts: Do I need an inititalization vector if I don't care about message leaking?

texts:
In Safety of a private key when knowing the full content of an encrypted message in case of fixed initialization vector, an answer says

using a fixed IV is bad practice since it allows statistical analysis attacks (read about it here). While K may not be leaked, M might leak from statistical patterns.

In my situation, someone needs to send my web application a short numeric id like 12345 so I can log them in as a user with that id. I'm not sure if I care if an attacker could work out what those id's are, because all it would tell them is that there is a record with id 12345 in the system, and the id itself is meaningless.
Also, in the wiki article, the statistical attack does recover the original image, just aspects of it due to repeated blocks. But there the original image has repeating blocks of similar data. Would this be any issue if the message is just a short identifier like 12345?
In such a situation, can the IV be constant (do I need it at all)?


texts:
Do there exist any zkSNARK constructions that are based on post quantum cryptography?

The encryption scheme used in the zkSNARK that is employed in Zcash for instance uses an encryption scheme of the form $E(x)=g^x$ for some generator $g$ of an elliptic curve group.


texts: Why does PHP crypt give this unexpected result

texts:
So I have this PHP code,it is meant to encrypt a users password...
Three problems/questions:

My 'salt' CHANGES ITS NAME
I get the same result
Is this actually how the result is meant to be?

PHP CODE

<?php
$password=$_POST['password'];
?>

<?php
if (CRYPT_BLOWFISH == 1)
{
echo "Blowfish: " . crypt("$password", '$2a$09$anexamplestringforsalt$');
}
?>

RESULT:

Blowfish: $2a$09$anexamplestringforsaleU79j3Xck4QHAVNZ.exkIn8ZZrZnIrHq

As you can see, my salt goes from $anexamplestringforsalt$ to $anexamplestringforsaleU. (Or is that supposed to happen?) Also, that is the same result I get even after changing the password.

Please help.