texts: A modification of the Blum-Micalli construction

texts:
Consider the following modification of the Blum-Micalli construction (denoted by BM):

$G_l(x) = f^l(x) || BM^l(x)$

I am asked the following questions about it:

Show it is a PRG of fixed stretch for every fixed $l$ polynomial in n.
Discuss the advantages/disadvantages of outputting also $f^l(x)$.
In particular, consider the case when a trap door permutation is used for $f$ and the resulting PRG is used within the pseudo random one time pad.

As an advantage I would say that this PRG gives $n$ more bits than plain Blum-Micali construction. However, I'm not sure how to handle the rest of the questions. Could you provide any hints?

Notation

$BM^j(x) = hc(f^{j-1}(x))\| \ldots \| hc(f(x)) \| hc(x)$

where $f: \{0,1\}^* \to \{0,1\}^*$ is a permutation on $\{0,1\}^n$ for every $n$ with hard-core predicate $hc$ and where $f^j$ denotes the composition of $f$ with itself $j$ times.

Solution

In this document you may find an answer as discussed in my class. I will still appreciate the effort to create a publicly available and pedagogic solution to this problem. Once it is here, I will remove the link.

One question that I still have is if the concatenation of unpredicatable functions is unpredictable.


texts: Cascading encryption with blocks or output

texts:
For educational purposes, I'm trying to build a cascading encryption implementation with AES, Twofish, Blowfish, Salsa20, and ChaCha20. First of all, please don't judge my paranoia or choices, this is just for learning. I don't remember exactly where, but I think that A(B(C(plaintext))), where A, B, and C are ciphers, is bad, because you're putting one cipher in front of another and creating a larger attack surface. I remember hearing that it is better to encrypt each block with A, B, C in CTR mode and then combine: A(B(C(block1)))+A(B(C(block2)))....
Is this true? What is the most optimal way to implement cascading encryption? Thanks.
Edit: Can anyone find a JS implementation of Serpent? I can't find an implementation anywhere.
Example:
I want to encrypt "Hello world, why am I writing this".
Method 1 (A(B(C(plaintext)))):
Ciphertext =
Twofish(Serpent(AES("Hello world, why am I writing this")))

Method 2 (A(B(C(block1)))+A(B(C(block2)))...., suppose block size is 8):
Ciphertext =
 Twofish(Serpent(AES("Hello wor")))
+Twofish(Serpent(AES("ld, why ")))
+Twofish(Serpent(AES("am I wri")))
+Twofish(Serpent(AES("ting thi")))
+Twofish(Serpent(AES("s0000000")))

Which would be more secure, if there is a difference?


texts: TLS-conformant ciphertexts and SSLv2-conformant ciphertexts for Blechenbacher attack for DROWN attack

texts:
This is regarding the published paper on the DROWN attack (https://drownattack.com/drown-attack-original-report.pdf)

It was mentioned in the paper that for TLS, RSA PKCS#1 v1.5 is used to encapsulate the 48-byte premaster secret exchanged during the handshake. Does means that  a random padding string PS is prepended to the 48-byte premaster secret to this formatted massage

([00] || [02] || PS || [00] || pms)

before the actual RSA encryption is done?

If yes, I have 2 questions

(1st question)
How does the decryption oracle in the SSLv2 server differentiate between TLS-conformant ciphertexts and SSLv2-conformant ciphertexts, since the padded TLS plaintext also contains ([00]||[02]) as the 1st 2 bytes?

(2nd question) Why is it that one has to transform a RSA PKCS#1 v1.5 TLS conformant ciphertext to RSA PKCS#1 v1.5 SSLv2 conformant ciphertext before being fed to the Blechenbacher oracle?

Thanks in advance!


texts: Is RSA signature as strong as the RSA encryption?

texts:
Is it proven that breaking RSA signature is as hard as breaking the RSA encryption, considering the same key size?

I know that they both are based on the RSA function, but I believe that, as always with cryptography, the answer can't be that simple.

First, technically, RSA signing and RSA encryption use different exponents: the former uses a private exponent, and the latter uses a public exponent (which is typically smaller).

Second, padding schemes do matter - but I'm assuming in my question that a "good" padding scheme is used - for instance, for signatures it's RSA-PSS or RSASSA-PKCS1-v1_5 (the latter is non provably correct, but it's still widely deployed and not actually cracked yet).

Third, does the answer depend on the allowed usages of the RSA keys in question? I.e. comparing situations: a) having two keys, one restricted to only Digital signature, and another to only Key/Data encipherment, b) having a single key, with both usages allowed.

Any references to books/standards/conference presentations will be appreciated.
Thanks!


texts: Does omitting the first two lines of RC4's pseudo-random generation algorithm weaken the cipher?

texts:
A particular educational software program published by a U.S. government agency uses a variant of RC4 to obfuscate its data files (see Stack Overflow question). The variant of RC4 in question is identical to standard RC4 except at the beginning of the pseudo-random generation algorithm. The developer omitted the first two lines below (from Wikipedia's description) because he based his code on an erroneous implementation from Planet Source Code from around 2005.

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile

Thus, i and j retain their final values from when the key scheduling algorithm ran (i = 256, not 0, and j = (j + S[i] + key[i mod keylength]) mod 256 from when i = 255 during the KSA).

In this case, the encryption provides no actual security because the key is hardcoded into the software, but suppose the developer had used the code to encrypt a secret file on his hard drive. Does this implementation error significantly weaken RC4's strength?


texts: How to encrypt a message such that it cannot be decrypted before a certain time?

texts:
Suppose you have a message $m$ and you want to design a protocol that produces an encrypted message $c$ such that it cannot be decrypted before a certain time $t$ has passed from the encryption.

How would you realize this? What assumptions do you need?

I am just curious about it and I would like to discuss ideas (I have no clue if it is even possible).

Note that I am less interested in solutions that simply requires an amount of computation for descryption (assuming a certain amount of computing power) such that it takes a time $t$ to decrypt. Then, I suppose a kind of third-party/authority is required. What about a smart contract?

Look at it as a non-physical version of a timelock.


texts: Would this authentication on a Diffie-Hellmann-key-exchanged channel work?

texts:
Before I ask my question, let me say that I don't know the math behind OTR, so I don't know if the process of authentication in OTR is any similar to this.

Alice and Bob have exchanged keys using Diffie-Hellman key exchange
There's a man-in-the-middle - Eve.
This is the encryption "circuit": Alice -- e_alice -- Eve -- e_bob -- Bob
Both Alice and Bob use e to express the encryption key they use.
Thus in conditions where there is no MitM, e_alice == e_bob
Alice wants to verify that there is no MitM, so uses a verification question (and an answer) (like OTR in XMPP):

Q: Do you have a cat?

A: Yes

Note: Obviously use strong values for A. Don't ask about the presence of a cat, but rather cat's name (ideally if it's a unique name containing numbers and special characters) :P

Alice sends Q to Bob
Bob sends hash(e_bob+A). hash is any safe hashing algorithm, e_bob is the encryption key Bob uses, and A is the answer, salt in this context.
Alice compares received == hash(e_alice+A). In case this is true, there is no MitM.

In this context:

The hashing algorithm for zero-knowledge-proof
The encryption keys are a pre-shared (by the key exchange) secret
The answer is used as salt (while being another pre-shared secret), so Eve can't think: "Oh look, that's a sha1 hash. Let's try to crack it. Oh look it's our encryption key -- that's a no-go"
Possibly add additional encoding like base64 to minimize chance of hashed contents being in wordlists. (hash(base64(e_bob+A)))

Question: Are there any serious vulnerabilities, or would this work for authentication for insecure encrypted channels?


texts: "Strict" software for playing and learning with private and public key

texts:
my question is just for teaching/learning practice and I think it's not meaningful for the real world.

I've played with openssl a lot but from my understanding it's somehow not strict in the format of the input because it's capable of understanding different format or doing some operations not transparently to the user.

Getting to the question: is there way by using openssl to get just the private key from the key pair and from that private one to compute the public key? An example:

When I do openssl rsa -in private.key -pubout I know that openssl does not compute the public key from the private but it just extracts the information that is alredy stored in the keypair (private.key is indeed a store for the pair).

Also openssl pkey -in private.key -text claims to extract the private key but how I can be sure that it's not another keypair storage? Ideally I would use another software than openssl that IS stricter with the input it receives and feed it with the private key and that would complain if as input it's given the keypair.

It might be that the confusion I'm trying to clear comes from the fact that maybe I'm missing some details of the cryptography but I'd like to check that by playing with different softwares (i.e. encrypting data with one software and decrypting it with another), again a software that is strict about what it gets as input, in another terms not-user-friendly but learner-friendly :-)

For software I prefer to have something at hand and not to compile anything.

Thanks for reading till here :-)

Alex


texts: Is there a protocol for granting access rights to publicly stored encrypted data?

texts:
Alice is a data provider and Bob and Charlie are consumers.
Alice has a set of data assets $A_*$. Alice wants to share some of her assets with Bob, some with Charlie (they are not necessarily mutually exclusive).

Apart from the common assets she has shared between Bob and Charlie, she doesn't want the adversaries to access each-others access-restricted data assets.
Say if Bob has been given access to $A_1, A_2, A_3$; and Charlie has been given access to $A_3, A_4, A_5$ Bob should not be able access $A_4$ and $A_5$.

Alice also wants to be able to withdraw the access she has granted to adversaries. Say, Alice revokes Charlie's access to $A_3$, even though Charlie used to have access to $A_3$ he should no longer be able to access $A_3$ once his access is revoked. (Note: Charlie might have pro-actively backed-up the data somewhere prior to his access being revoked, we assume they have no means of doing that, or we simply take that risk)

Even though Alice has some means of secure channels between Bob and Charlie, she doesn't have the bandwidth to handle transferring the data she has. Alice wants to place the data encrypted in a public place and issue certification to adversaries to decrypt the data at will.

One solution I have in mind is as follows:

Alice encrypts all her assets with a different random key. And uploads the encrypted data to the public storage.
Whenever she wants to grant access to any of her assets she simply provides the key and path of the data to any of the adversaries.
When she wants to revoke the grants to a specific asset, she deletes the current encrypted version of the asset and issues a new encrypted version and uploads it. And shares the new key with other adversaries that still has access rights to it.

However in this protocol, the overhead of revoking someone's access is quite a burden. We would like to avoid re-encrypting the data. Not sure if there are solutions and schemes that can be employed here, but I'm curious to know if a better protocol exists.


texts: Concept of hashing a group of data and validating if a value exists within the group

texts:
When learning about cryptography and hashing, I remember seeing a concept where you could hash a number of values (ID's for example) and then validate against the hash, not storing the original IDs. Upon researching this further, I cannot find any concrete examples.

I am wondering if I misunderstood the concept when originally learning about hashing. Please review the following scenario and let me know if I misunderstood or the concept exists:

Concept

A university is running a contest for students. The university staff chose ten random student IDs as winners. Students can visit a website and enter their student ID to see if they won.

The winning student ID's are not stored in a database but rather are hashed. When a student enters an ID on the website, the ID entered is validated against this "winning hash."

Questions

Is this type of "group of values" hashing and validation a concept that exists or did I misunderstand something in my research?
If this does not exist, would the correct method be to hash each winning student ID, then when a student enters the ID to hash it and validate it against the individual stored hashes?

Thank you!


texts: How do I encrypt a long message using ElGamal encryption correctly?

texts:
According to ElGamal encryption, in order to encrypt a message I need to generate a shared secret s and after that I am to calculate c1 and c2 that are the final encrypted data. But what if my message is much longer than the bitness of the encryption system? I could split the message into many chunks and encrypt them separately.

Would it be correct to use the same shared secret for all these chunks?
Or I have to generate separate shared secrets for each chunk?

The first option would be preferable because it is much less expensive, but naively it looks less secure. Does this option have any vulnerability? Is there any research where I could read about it?


texts:
Could anyone guide me on how to implement FPE (Format Preserving Encryption) for Email address masking?

For example: if my ID is Poornima1@gmail.com then it should be encrypted something like   asdfghjk4@zxcv.qwe

Preserving the format and datatype.


texts: Why do key fobs/garage doors openers use rolling codes instead of PGP or SSL encryption?

texts: Wouldn't they be more secure if they used the same encryption technology computers use for remote access?


texts: Are NIST's changes to Keccak/SHA-3 problematic?

texts:
NIST is working on standardizing SHA-3.  They have selected Keccak as the basis for SHA-3, and they plan to make some small changes to it; the result (with NIST's changes) will be standardized as SHA-3.

A blog post from the CDT raises concerns over those changes.  Two specific concerns were mentioned:

The security level is "reduced": instead of offering 224-bit, 256-bit, 384-bit, and 512-bit versions of the hash (as found in the Keccak submission), the SHA-3 standard will only offer 128-bit and 256-bit versions.
Some of the internals of the algorithm have been tweaked by NIST.

My question: Are these criticisms of SHA-3 valid?  Are they something to worry about?

(To be clear: in the two points above, I'm just repeating what the blog post said.  I'm not trying to claim that those two criticisms are valid -- indeed, whether they are fair criticisms or not is exactly what I want to know.)

NIST gives the rationale for these changes in their presentation at CHES 2013.

I wonder if the first criticism might be a misunderstanding; is it an accurate statement of NIST's plans?  (See also Why restricting SHA3 to have only two possible capacities?.)  The second criticism might be more interesting.  Is there any technical merit to the second criticism?  Is there any reason to distrust the plans for SHA-3, or to suspect shenanigans?  Are these changes to Keccak more likely to make it more secure, or less secure?


texts: What (Where) is the formal definition of Multiparty Computation?

texts:
I'm just curious where we can see a (original) formal definition of MPC.
What (Where) is the formal definition of MPC?

We have a bunch of tools to build a MPC protocol.
Is oblivious transfer (or OT-extension) a part of MPC?


texts: A Construction of a Cipher from a Single Pseudorandom Permutation

texts:
A paper from 1997 A construction of a cipher from a single pseudorandom permutation proposes a cipher in which The message block is XORed with K1 before applying F [a single random permutation], and the outcome is XORed with K2. The authors state We show that the resulting cipher is secure (when the permutation is random or pseudorandom)

I found one paper Limitations of the Even-Mansour Construction that describes its severe limitations, but it still provoked some questions:

Is there any means to make a similarly simple cipher secure (even in theory)? How?
Might repeating further rounds make it secure against DCA?
Is there a similar cipher that 'is' useful by modern standards?


texts: Why is the private key generated first in public key crypto?

texts:
I'm still new to public key crypto. I'm trying to understand how it is that the private key is generated first in public key crypto? I would have expected the private and public key to be generated at the same time, as they would depend on each other.

For example, in a Bitcoin wallet, I can choose a private key (brain wallet), which will then be used to derive my public key (then my BTC address).


texts: Combining a block cipher with a (pseudo) OTP

texts:
One of the drawbacks of OTP is that it can require an inconveniently long key. Besides that, it doesn’t provide data authentication. Therefore, I have been working on an algorithm idea, which I hope to be more powerful and efficient than OTP:

Encrypt plaintext with a block cipher (something with strong avalanche effect and strong pseudo random output.)
Encrypt a random part of the ciphertext with a random pad which has a random length.

I hope my idea to have the following advantages over OTP:

it requires a short key consisting of three parts: one for the block-cipher, one that tells which part of the OTP to use, and the OTP itself. It's extremely small when compared to the key length of an actual OTP, but I think it is worth the burden.
It provides data authentication (due to the usage of a block-cipher).

So, the idea is built on the fact that each and every ciphertext bit is required to decrypt, or even break, a block cipher encryption. With some unknown part locked away with OTP, it will be impossible to obtain each tiny bit of the block-cipher-text, without the key.

Besides that, I think additional security may come from the fact that the part that was encrypted with OTP can not be recognised, because the block cipher output is (better: has to be) pseudo random. Bruteforce seems to be out of reach, as there are more possible chances than OTP (that's because the attacker doesn't know where the OTP was used).

TL;DR

All in all, you could say I have this idea of combining a block cipher with a (pseudo) OTP, trying to gain security and data authentication from that combination. Is there anything that seems obviously wrong with that? Some crucial aspect I may be missing? Are there any specific security issues?


texts: Is Porticor's "homomorphic" key encryption something that can really be done or is it just marketing hype?

texts:
Porticor has an interesting file encryption offering for encrypting and decrypting files in an MySQL database quickly.

They are an Amazon AWS (Amazon Web Service) Partner Network technology partner and their product is available in the AWS Marketplace.

It seems similar to Gazzang's zNcrypt.

Porticor has been touting for a while that it will be offering homomorphic key management. That sounds very interesting and appealing, but it seems to be taking them a long time to roll it out.

Is it theoretically feasible for them to implement this, or is it just marketing hype? I'm beginning to wonder.


texts: In AES-256-CFB, does using a pseudo-unique key circumvent the weakenesses of reusing keys?

texts:
Disclaimer: I'm not very familiar with the subject. Apologies for how that reflects in the question.
Goal: Encrypt multiple messages using the same key
Hypothesis: If we use, as the actual encryption key, a reused secret key concatenated with a publicly known yet varying (and never repeated) part, would that prevent exploits based on key reuse?
For example,
INPUT
- secret_key
- plain_text

ALGORITHM
- pseudo_key = SHA(plain_text) + secret_key
- initialization_vector = SHA(plain_text)
- encrypted_message = SHA(plain_text) + Encrypt_AES-256-cfb(pseudo_key, plain_text)

DECRYPTION would naturally be:
plain_text: Decrypt_AES-256-cfb(SHA_part_of_encrypted_message + secret_key, remaining_of_encrypted_message)

Let's suppose a resourceful attacker knows the algorithm and has access to 100 used messages
Would he/she be able to crack them? (taking into account the procedure above, and specifically, that the secret_key is the only unknown)
If he/she would, could a different base encryption algorithm make this stronger? Or another method/procedure?
I assume that this doesn't make it any safer, otherwise a similar procedure could be incorporated in the encryption algorithms themselves.
Nonetheless, it is not clear to me how some attacks mentioned in the context of key-reuse could work given that the actual encryption key would be different.
Is there any mode of operation of any modern cipher - if needed in combination with a procedure like the above - that allows us to reuse the same "secret" key without introducing vulnerabilities?
EDIT
(in light of Paul Uszak comment about a leaky initialization vector)
If I understand correctly, the comment means that according to the procedure above identical plaintexts will have the same initialization vector and key (which is constant, "by pre-condition/setup") and therefore the same encrypted text, which in turn is a weakness (?).
Assuming this interpretation to be correct, I'd like it if we could consider the following adaptation to the procedure:
INPUT
- secret_key
- plain_text

ALGORITHM
- R = randomNumber (e.g. Rand(0000-FFFF))
- pseudo_key = SHA(plain_text + R) + secret_key
- initialization_vector = SHA(plain_text + R)
- encrypted_message = SHA(plain_text + R) + Encrypt_AES-256-cfb(pseudo_key, plain_text)

DECRYPTION:
- plain_text: Decrypt_AES-256-cfb(SHA_part_of_encrypted_message + secret_key, remaining_of_encrypted_message), with SHA_part as IV

Note that:

"R" could be used only in the initialization_vector (and not in the pseudo_key also). I used it in both to "simplify" the full message transmitted. Please let me know if either including it or not in the key part impacts strength/vulnerabilities in any way.
Perhaps "R" could be a "top-level part" of the initialization_vector (instead of part of the argument of the SHA). But I'm not sure whether the fact that the attacker knows how the SHA of the plain_text and the random number are combined to form an initialization_vector (the whole procedure is public) would help "cracking something", having access to multiple encrypted messages (with the same sacret_key, same plain_text, and where the random number would also be transmitted "publicly").

In any case, focusing on the actual procedure, and not in the notes above:
Would this random component make the procedure stronger?
Evaluating the procedure as a whole and going back to the initial question:
Does this procedure circumvent the weaknesses of reusing keys when the attacker has access to multiple messages encrypted using the same base key?
Thanks in advance.


texts: Using the security definition in the malicious model to prove security in the semi honest model

texts:
Can I use the security definition in the malicious model in order to prove the security of a two-party protocol which is in the semi-honest model? (I am using IDEAL/REAL Model paradigm)

Would you please explain it to me?

These definitions are from "Efficient Secure Two-Party Protocols-Hazay-Lindell"
Definition 2.3.1 (Malicious model)

Definition 2.2.1 (Semi honest model)

-


texts: What different type of code should I use to decode this string?

texts:
Just saw this string of letters:

picture

here's a raw text version:

bgedrf,jeidiqghe
gq-gfdchcubfe--q
iqhogmebhbiehc
ticdcf

x

geheedajftc,dieieff
hggyiddifeetshdccf
cdxhd-hcvddhie-cgi
efgfih-rlixeffeii-hd
feigfg

someone has already tried a Caesar Cipher, but I'm not exactly an expert on encryption and cryptography.

wondering if y'all might be able to recognise any significance. There could be numbers involved (because of the "x" which i would assume means "times".


texts: Is factorization modulo a product of primes an NP-hard problem?

texts:
For example, let, $p$ and $q$ be two large prime numbers. We set $n = p \cdot q$.
Now, let $a \cdot b = c \pmod n$.
Given $c$ and $n$, is finding the factors $a$ and $b$ computationally difficult?

I can alternatively ask, is integer factorization modulo a product of primes an NP-hard problem?


texts: Cryptographic data structure: sparse array without membership test

texts:
I would like a data structure supporting two operations: $\mathsf{set}(k,v)$ and $\mathsf{get}(k)$, with the following properties:

$k$ can be any number between $0$ and something impressively large, like $2^{256}-1$.
If there is some $v$ such that $\mathsf{set}(k,v)$ has been called then $\mathsf{get}(k)$ returns the most recent such $v$.
There is no way to learn anything about which $k$ and $v$ are such that $\mathsf{set}(k,v)$ has been called (but it might be possible to determine information that does not have to do with specific $k$ and $v$, e.g., it might be possible to learn how many times set has been called or on how many different $k$ it has been called).
Space and time complexity are bounded by reasonable functions of the total number of calls to set and get (or better yet by a reasonable function of the number of keys set has been called on).

An attacker would learn everything I know, so the solution cannot be based on me retaining any secrets.  But an attacker would not see the sequence of $\mathsf{set}$ and $\mathsf{get}$ operations since that would allow knowing what $\mathsf{set}$ has been called on.  An example of a data structure that would meet all my demands except for the computational complexity ones is to create at time zero an array of size $2^{256}$ populated by random data and then update and query it as a normal array.

I assume a fixed field length for $v$ and also that the data being stored in $v$ is effectively random.  The meaning of the last statement is a bit subtle.  If $v$ is a 256-bit field then storing all zeros in a place in the array will effectively give away that it has been set.  If $v$ is a 1-bit field then storing any particular value in any particular place will not give anything away, but other patterns, like storing more zeros than ones might.  Imagine that the attacker has a correct guess about what the set of set keys is.  Depending on how the array was used, he might be able to become more certain of his guess by querying the array.  I simply want a data structure that doesn't give up any more information than strictly necessary beyond the infeasible full array of length $2^{256}$ initially stocked with random data.

Obviously it will have to give up a little more information because it will get bigger depending on how much data it has in it (compare black holes), but ideally the approximate number of keys set is all the information it will leak.  Actually, it will not have to progressively give up more information if the maximum amount of data the structure can contain is fixed at creation time.  And the partial solutions to the problem that are given below by otus and myself require the size to be fixed in this way anyway.

Is there such a data structure?  Also, what is a good reference for this kind of question?

The attacker only gets to see the final data structure. The concept of history-independent data structures looks really interesting, but I am skeptical that literature will help with my problem. Among other things, the couple of papers I looked at seemed to use a threat model where the attacker has infinite computational resources, but it is impossible to solve the problem under that threat model.


texts:
I was reviewing RSA by hand.
I picked 53 and 59 as my primes.
For e I picked 5.
When I solved for d using extended euclid, I got 1 which obviously doesn't decrypt anything.
I checked my answers online using calculators and got the same result.
Did I pick e or a prime wrong? How do I make sure I don't get 1 as d?


texts: Understanding hybrid cryptography's concepts: signing and CA

texts:
After learning about symmetric encryption, public-key encryption, one-way hash, digital signature and digital certificate, I was tasked to think of an imaginary hybrid cryptosystem. I was thinking along the lines of this:

Alice and Bob agrees on a shared private key that is to be used to encrypt (using encryption algorithm like AES) messages
To reach private key agreement, Alice and Bob will use DH
Alice now wants to send the message p to Bob
To ensure that Bob can verify the message p comes from Alice, Alice will sign the message p.
Because signing requires a lot more resources and can only typically only sign a message with a limited amount of length, Alice will first hash (say using SHA-1) then message p to a message digest called md1. The message digest md1 is then signed by Alice (using some signing algorithm like RSA). This message digest md1 now contains a digital signature and will be called s
Then, Alice will send both the original message p and the signed message digest s after encrypting them using an encryption algorithm (say AES) using the private key that was agreed upon during DH. Alice also sends the required information in regard to verifying the signature.

Now the message sending process is done. It's Bob's turn to receive the sent packages:

Bob will receive and encrypted original message p and signed message digest s
With RSA, Bob can convert the signed message digest s back to message digest md2
To verify that the message has not been tampered with midway, Bob will now hash using the same hashing algorithm (in this case, SHA-1) from the sent original message p to create another md3
Bob then checks if md3 and md2 are the same or not. If they are, they are from Alice. If they're not, Bob will ignore this message
Bob has now received the original message

I was thinking along the lines of the above, but some points went over my head.

Questions:

Bob magically knows that the algorithms used are SHA-1, RSA and AES. How do Alice and Bob agree on the algorithms used in the whole process?
When I'm hashing and signing, I'm providing integrity and authentication at the same time. Are these two processes inseparable if I want to provide both aspects? I'm assuming that you always sign the message digest because of efficiency problems (as mentioned above), is this correct?
The very first step of DH is to exchange a public key generated by Alice and Bob. To do that, they will need to agree on an initial large prime number pn and its prime generator g. Then, I will send the public key generated by both sides. However, as I will be exchanging messages, how do I know that the agreed pn and g are not tampered by others and that the public key sent from both sides are indeed from themselves and not an attacker? Do I need to sign these message exchanges?
As you can see in my example, I have failed to involve a CA in my imaginary hybrid cryptosystem. In my understanding, a CA will verify that messages are indeed from a company/person. To verify the messages are from one side, CA will see the digital certificate that is sent alongside the message. However, why do I need to involve a CA when I can sign a message myself and ask the receiver to verify the signed message? Why involve a third-party?


texts: Why are the random exponents so much bigger in the Socialist Millionaire protocol versus Diffie-Hellman key exchange?

texts:
Section 8, Security considerations, of RFC3526, which defines groups used for Diffie-Hellman has a table recommending some random exponent sizes. In particular, it says:

The strength of a key exchanged using the 1536 bit group has

about 90 bits strength for a 180 bit random exponent
about 120 bits of strength for a 240 bit random exponent

On the other hand, the Off-the-Record protocol spec, which uses that 1536 bit DH group, says:

  The random exponents are 1536-bit numbers.

I'm not adhering to the OTR spec, because I'm just using the SMP part of it. But I'm interested to find out:

What is the reason to use these comparatively huge random exponents, when a DH key exchange gets what I would call "enough" strength at far lower exponent sizes? I'm interested because 240 bit random numbers make the authentication go a lot quicker.

As a bonus: how does SMP using the 2048, or 4096 bit groups with smaller random exponents compare to using the 1536 bit group with large random exponents?


texts: How to specify last $t$ bits are only sent when a signature is sent?

texts:
I have read that in cases where there is a limit on the amount of data sent over the network, one idea is to sent only $t$ bits of data rather than sending all the bits. For example, in the Schnorr scheme this can be employed.

My question is, whether this can be specified by sending the $t$ bits along with the other information?


texts:
Why is lattice-based cryptography believed to be hard against quantum computer?

Learning With Errors(LWE) problem (reduction to SVP) is just one example.

Can you provide some intuition of the hardness?


texts: Advantages/Disadvantages of Bcrypt vs. hash/salt

texts: I have an application that I use sha3-512 to hash my password with a randomly generated 64 characters salt for each password. Is it bad to use this method to store passwords? I know many people reference using bcrypt for password storage. What are the advantages/disadvantages of using bcrypt vs. a hash/salt combo?


texts: Bitwise method of generating r for RSA-KEM

texts:
It seems that RSA-KEM has a very troublesome method of generating the secret $r$. It seems that the random value needs to be in the range $0 \le r \le {n - 1}$.

Now most cryptographic environments don't have a random number generator that generates those kind of numbers; usually they are just provided with a seeded DRBG that outputs full bytes. Performing all kinds of integer operations on the bytes may lead to leaks of the master key within these kind of environments. Especially the $\bmod$ operation seems to be tricky in this regards.

Is there a known good way of generating $r$ that disposes of the $\bmod$ operation and possible looping?

For instance I could think of constructing $r$ as

00 | R

The | operation is of course concatenation.

In this construction $R$ is then an octet string consisting of (pseudo) random bytes. $r$ consists of the value of 00 | R when used as a big endian unsigned integer. It can be used directly as input to raw "RSA encryption" as implemented by most libraries.

That would provide $\operatorname{len}(R) * 8$ bits of entropy for the KDF. I think that would be $\lfloor (log_2(n) - 1) / 8\rfloor \cdot 8$ bits of entropy when measured against the modulus value $n$.

The scheme would otherwise be unaltered of course; there would be no explicit checks on the value of $r$ during decryption.

Would this suffice as a secure scheme of constructing $r$ instead of performing integer calculations and checks to get to $0 \le r \le {n - 1}$?


texts: E0 is used for encrypting Bluetooth communication, and it is initialised with a key of at most 128 bits. How secure is E0, and what are the E0 encryption attack vectors?


texts:
Can anyone decrypt ciphertext using a public key? I always thought we can only decrypt using a private key. In that case, what does this line in the RLPx documentation mean?

Receiver receives the initiator handshake and decrypts it with its own public key.

Is the author talking about verifying signatures?


texts: In DES key schedule some rounds use one left shift while others use two left shifts. What is the reason behind this?


texts: How to get the key data from the pkcs#8 format?

texts:
Being newbie to crypto, I understood that RSA keys are shared are pairs $(e,n)$ or $(d,n)$. But when I was given a doc with keys, they were in PKCS#8 format.

How to get the keys out of this format?


texts: How do we prove that AES, DES etc. are secure? I've read about them and know the basics on how they work, but I still don't quite understand how we can be sure they are secure? What are the proofs?


texts:
Im studying for my final, and some of the practice problems that I have found have discrete logarithms in this notation $L_n(p)$.

What does this notation equate to?

For example:


texts: How fast can a SHA-256 implementation go?

texts:
I'm looking for high-speed SHA-256 implementations, and specifically, ones with low latency; that is, the time between when you submit the message block, and when the output (or internal state) is produced.

I've googled it, and the fastest I've found appears to take circa 70nsec; does anyone know of something faster?

Now:

I'm not interested in parallel implementations (which can obviously do far more than 1 hash every 70nsec); I am specifically looking for a single high-speed hash.
An ASIC implementation (or even a proposal that gives a plausible outline of how fast it would be) would be quite acceptable.
We can assume that the preimage fits within a single SHA-256 block (or that we're just doing the compression function itself).
An alternative way of answering this would be 'how fast can we compute SHA-256 on a single large message'; can we do something faster than about 1GByte/second?
I specifically asked about SHA-256, however if someone has something similar about, SHA-3 or AES, I'd be interested in hearing that as well.

Thanks!


texts: In which situations is a length-extension attack a problem?

texts:
A lot of hash functions, including the SHA-2 family(but not the SHA-3 candidates and SHA256d) are vulnerable to length extension attacks. But when is this property a problem?

I guess certain naive MAC implementations might have issues. Are there also some situations where length-extensions cause problems for unkeyed hashes?


texts:
I am looking at Wikepedia Galois Counter Mode article. I see this diagram

I am trying to figure out where the IV works its way in. Is it used to initialize the counter? If so, how does a sequence of 12 bytes (96 bits)initialize a counter on a 32 bit machine?


texts: Is (1 bit HW signal) XOR (8 bits PRNG output) sufficient for a HWRNG?

texts:
This is really a follow   up question   to a comment made regarding How to roll a HWRNG

In the situation of whitening a hardware generated random bit stream, "XORing the two bitstreams should be fine for mixing, by the piling-up lemma" was said.  The other bit stream was suggested to be one from a PRNG.

In signal sampling, it is rare to use the full range of ADC bits.  This is to avoid clipping the signal or saturating downstream amplification stages. Amplifier internal noise is typically related linearly to the input signal level, so more signal, more stray noise of the unintended variety. So for example in extremis, the hardware may only be sampling with a 1 bit width.

The PRNG will in all likelihood be outputting standard octets.

So the question arises, is

(1 bit HW signal) XOR (8 bits PRNG output)

sufficient to whiten a hardware random number generator, simultaneously ensuring that it's still a hardware generator rather than just a pseudo generator?

Side question:  would the PRNG have to be cryptographically secure or not? Consider that the system's numbers could still not be predicted with a simple RND() type generator due to the unpredictability of the hardware signal.


texts: What to learn in order to understand Weil Divisors

texts:
My current role as a software developer is leading into areas of research in elliptic-curve-cryptography that keeps bringing me back to bilinear pairings.  This includes BLS Signatures, CL Signatures and zkSnarks.

In learning PBC, I've found I need to understand Miller's algorithm, but I lack the mathematical background to fully understand the concepts of divisors, (zeros and poles on elliptic curves etc.)

Has anyone faced this issue? If so, can you save me possibly weeks of work, and point me in the direction of accessible resources that I should digest in order to understand Weil divisors?

Is it possible to understand the required theory without learning linear algebra / abstract algebra and algebraic geometry?


texts:
Am I losing any entropy when using KDFs, such as the ones in NIST Special Publication 800-108?

For example, can I derive 128-bit session keys from a (uniformly random) 128-bit master key?


texts: Length of ElGamal signature compared to RSA signature

texts:
In his original work (1) on the ElGamal encryption and signature scheme Taher ElGamal states in chapter V. section B.:

  For  the  signature  scheme  using  the  above  arguments  for   the
  sizes of the numbers in our system and the RSA system,  the  signature
  is  double  the  size  of  the  document.  Then  the   size  of  the
  signature  is  the  same  size  as  that  needed  for  the   RSA
  scheme, and half the size of the signature for the new
  signature scheme that depends on quadratic forms [...]

However, I was under the impression that (schoolbook) RSA signatures have roughly the same length as the corresponding modulo n, while ElGamal signatures are roughly twice the size of their corresponding modulo p.

Could somebody please clarify?


texts: Efficient Robust Private Set Intersection Additive ElGamal

texts:
I am trying to implement Efficient Robust Private Set Intersection using additive ElGamal.

I am trying to run the full protocol mentioned in Section 3.4 on the following inputs:

$p = 17$ (prime)
$g = 6$ (generator)
$x = 5$ (private key)
$k = g^x \pmod p = 6^5 \pmod{17} = 7$ (public key)

Suppose the clients inputs are 1, 2. Then $P(x) = (x-1)(x-2) = x^2-3x+2$, and therefore the coeffiecients to encrypt are $(1, -3, 2)$. I chose $y = 10$ and so the encrypted values are:

$1$ becomes $(15,12)$
$-3$ becomes $(15, 1)$
$2$  becomes $(15, 4)$.

The Server Side Input Set $S=\{1\}$ and the random value $r0$ corresponding to $\{1\}$ is $r_0=2$.

With the above problem in context, I have some questions:

What does P 0,j refer to in Step 7. Can you please give an example?
In Step 8, suddenly variable i is introduced along with j. What does i, j, refer to?
In Step 8, ENC() function has a ; in between. How do we interpret ENC(a;b)?


texts: How to construct inequality, padding, and truncation in R1CS?

texts:
I'm trying to reimplement the zkSNARKs used in zcash using the libsnark library. It involves checking for inequality, and bit manipulation such as padding and truncation. How do I implement those in R1CS?
I saw this answer which suggested computing inequality via bit decomposition. How do I do bit decomposition in R1CS?


texts: Why is a smaller value preferred for the public key in RSA?

texts:
For my practice implementation of the RSA cryptosystem I use a random value generation function such the value of public key e holds:

The public exponent $e$ and the modulus $n$ should be $e<\phi(n)$
$e$ and  $\phi(n)$ are coprime, $gcd(e,\phi(n)) = 1$

Although this works satisfactorily, the algorithm returns values of $e$ which are very large in magnitude which, apparently, is undesirable.

Why is it preferred to generate smaller values for the public exponent in the RSA system?


texts: How do I convert the definition of E-521 into a curve definition a la Bouncy Castle?

texts:
I am currently trying to create an ECCCurve for E-521. Unfortunately, it is not currently a named curve in the library I am using, so I will have to define it manually.

I am using the definition of the E-521 curve provided here:

E521 is a curve over GF(2^521-1), formula x^2+y^2=1-376014x^2y^2,
basepoint
(1571054894184995387535939749894317568645297350402905821437625
18115230499438118852963259119606760410077267392791511426719338990
5003276673749012051148356041324, 12), order 2^519 -
3375547632585017057891076304187826360719049612140512266186351500
85779108655765, cofactor 4.

The two curve definitions I can choose from are FpCurve and F2mCurve. I'm not sure which one to choose for this. I have looked here. Unfortunately, I don't know how to extrapolate which one to use based just on the knowledge that E-521 is an Edwards curve.

Is an Edwards curve not compatible with the base classes that are defined in the library? Do I need to wait for further development there, or can I risk attempting to implement it myself? The latter is obviously a question I will likely have to answer myself, but some extra information on the risks/other implementations I could examine would be helpful.


texts: Difficulty of forging MACs based on linear functions over $GF\left(2^n\right)$

texts:
This is a homework question, therefore I'm not expecting full solutions, just general guidance.

I want to build a one-time MAC using universal hashing.

I defined my hash functions as:

  $h_{a,b}:\begin{array}{lll}
\mathbb{F}_{2^{n}} & \to & \mathbb{F}_{2^{n}}\\
x & \mapsto & ax+b
\end{array}$ for $a\in\mathbb{F}_{2^{n}}\backslash\left\{ 0\right\} $, $b\in\mathbb{F}_{2^{n}}$

Where $\mathbb{F}_{2^{n}}=GF\left(2^{n}\right)$ means the galois field/finite field of size $2^n$.

These functions have 0 probability of collision for two distinct messages.
However, in order to use these functions as a one-time MAC, I need to show security which is defined for the following game with adversary $A$:

  An oracle generates a secret key $a,b$, then $A$ can choose exactly one message $m$ to query, that the oracle tags for $A$ with $h_{a,b}\left(m\right)$). Then $A$ has to generate a message $m'\neq m$ and tag $t'$ such that $h_{a,b}\left(m'\right)=t'$.

Security is defined as for any efficient (polynomial) adversary $A$ allowed only one query (as described), there exists a negligible function such that the probabilty of $A$ winning the game is at most that negligible function.

This is where I'm stuck. I have intuition, but can't formulate a formal proof. I know that if $A$ decides to query with message 0, then he knows what b is, since
$a\cdot0+b=b$, but then he's left with guessing $a$ (need to show here he can't do it other than randomly guessing). And if he decides to query message $m$ that is not 0, he could at most calculate $\left(a\cdot m+b\right)m^{-1}=a+bm^{-1}$ which is the same problem (more or less) as $am+b$.

I would love some direction on how to approach such proof of showing finding such message with a viable tag, reduces to guessing at best (therefore showing an upper bound that is negligible).

Thanks!


texts: Authenticated encryption vs end-end encryption

texts: I am kind of new to crypto. can someone highlight the differences between authenticated encryption and End-to-End encryption


texts: Are all self-synchronizing cryptosystems necessarily self-synchronizing stream ciphers?

texts:
I have a noisy communications link between two points that occasionally deletes a byte.

By "self-synchronizing cryptosystem", I mean that the receiver attempting to recover the original plaintext will be mostly successful, with at most a dozen or so corrupted letters of plaintext corresponding to each missing ciphertext byte.

Are all such cryptosystems necessarily self-synchronizing stream ciphers?

In other words:

Cryptosystems that are some block cipher mode of operation:

A few block cipher mode of operation are self-synchronizing, such as the SCFB mode and OCFB mode described by Fang Yang and Howard M. Heys; "Comparison of Two Self-Synchronizing Cipher Modes". Do all such block cipher modes end up producing a stream cipher, i.e., producing a pseudo-random bitstream and then combining that bitstream with the plaintext using XOR (or another stream-cipher operator)?

Cryptosystems that are not some block cipher mode of operation

Do all such cryptosystems end up either being effectively a stream cipher, or are non-self-synchronizing, or both?

I realize this isn't a practical question --
in practice, we MAC the message as a whole, and if anything was changed, added, or deleted, we reject the entire message.
(In practice, non-crypto networking techniques handle bit-alignment, byte-alignment, packet-alignment, etc. and then re-send or otherwise correct occasional missing bytes and assemble the complete message long before any crypto algorithms at the receiver ever see that message).


texts: Pseudorandom zero-sharing: how does it work?

texts:
TL;DR

How can the shares of the PRZS protocol proposed in [CDI05] reconstruct the "secret" $0$?

Is the number of shares required to reconstruct $0$ equal to $2t + 1$?

Long question

The paper "Share conversion, pseudorandom secret-sharing and applications to secure computation." by Cramer, Damgård, and Ishai shows a protocol for pseudorandom zero-sharing that enables every player $P_j$ to locally compute his share $s_j$ of the polynomial $f_0$ of degree $2t$ from initially distributed keys $r_A^i$, where $t = k - 1$ in a $(k, n)$ secret sharing scheme.

$s_j$ is computed as follows:
$$s_j = \sum_{A \subseteq [n] : |A| = n - t, j \in A} \sum_{i = 1}^{t} \psi_{r_A^i}(a) \cdot f_A^i(j)$$

The authors say that: "it is straightforward to verify that this results in shares consistent with polynomial $f_0$" and that: "$\mathit{deg}(f_0) \leq 2t$ and $f_0(0) = 0$".

If I've correctly understood, if we make $f_A^i(j) = 1, j \in A$ and we consider $\psi$ as an HMAC function, then every player $P_j$ simply sums the HMAC of $a$ with all the keys $r_A$ he has received from all the sets $A$ he belongs to.

How can this result in shares (polynomial $f_0$) that can reconstruct the secret 0? It still remains quite obscure to me.

Furthermore, since $\mathit{deg}(f_0) \leq 2t$, does this imply that to reconstruct $0$ we need $2t + 1$ shares at most?


texts: Encryption method that is purposely vulnerable to cracking parts at a time?

texts:
Is there a method of encryption where your key is made up of $n \cdot s$ bits, but also such that an attacker would know when they've successfully cracked each $s$-bit part?

For example, the full key could be $\texttt{1011 0101 1010}$, for $(n=3, s=4)$and you would be able to know if you successfully guessed that the first four digits are $\texttt{1011}$?

Note the entire key could be discovered in $n \cdot 2^s$ time if you individually cracked each of the $n$ parts.

Think of it by analogy like cracking a combination lock by sound, where you would know when you successfully discovered the first number, then the second number, and finally the third number?


texts: Why don't we use MACs to store passwords?

texts:
These days, the best practice for storing passwords is to use a scheme like scrypt or bcrypt. The goal of these schemes is to make dictionary attack inefficient for an attacker but it also slows down legitimate use of the function.

If you're doing thousands of password checks per second, there is a real world cost of this slow down.

I'm wondering why we can't simply use a MAC? You choose a random salt, $s$, for each password you want to store. You then compute: $MAC(s || password, k)$ and stores the result and the salt.

This construction operates quickly and seems to me to have superior security properties to scrypt and bcrypt. The only draw back is that we now have to securely store $k$. This limits its usefulness in some contexts but not in others.

For password based file encryption, this scheme wouldn't be suitable but for storing passwords for a website, we can use a HSM device to keep the attacker from getting $k$.

Yet I've never seen any advice that suggest we store passwords in this way. Why is this?


texts:
First, I'm pretty new to the world of encryption. As I understand it, in WEP, the plaintext and CRC are XOR'd with the IV and the key (or more accurately, the key/stream, which is produced by a pseudo-random generator) to get the resulting ciphertext.

Basically, given two different messages encrypted with the same IV and key, an attacker can XOR both ciphertexts and soon reveal the plaintext.

So, why is the IV sent in plaintext with the message? When the attacker knows the IV, isn't it easier to work out the key and decrypt the messages?


texts: The backdoor of Telegram on Diffie-Hellman Key Exchange and possible other examples?

texts:
Diffie-Hellman Key-Exchange (DHKE) should be used carefully during the end-to-end encryption. A man-in-the-middle (MITM) attack is possible.
Standard DHKE
The simple protocol on the multiplicative version as this
Alice and Bob agree on the modulus  $p$ and a base $g$  ( For security see Safe Primes )
\begin{array}{lcl}
\text{Alice} & \text{Transmit} & \text{Bob}\\ \hline
a \stackrel{R}{\leftarrow} \mathbb{Z_p}& & b \stackrel{R}{\leftarrow} \mathbb{Z_p}\\
\text{calculates } A = g^a & \xrightarrow{A} & \text{calculates } B = g^b\\
 & \xleftarrow{B} & \text{calculates } s = B^a = (g^a)^b = g^{ab} \\
\text{calculates } s = A^b = (g^b)^a = g^{ab} & &
\end{array}
Therefore both sides have agreed on the $s = g^{ab}$ and
Man-in-the-Middle DHKE
Alice and Bob agree on the modulus  $p$ and a base $g$
\begin{array}{lcccl}
\text{Alice} &\! \text{Trans}\! & \text{MITM} &\! \text{Trans}\! & \text{Bob}\\ \hline
a \stackrel{R}{\leftarrow} \mathbb{Z_p}, A = g^a&  \xrightarrow{A} & & &b \stackrel{R}{\leftarrow} \mathbb{Z_p},B = g^b\\
  & \xleftarrow{T} & t  \stackrel{R}{\leftarrow} \mathbb{Z_p}, T = g^t & \xrightarrow{T} & \\
 &  &\!  s_{TA}\! =\! A^t\! =\! (g^a)^t\! =\! g^{at}\! \\
s'\! =\! T^b\! =\! (g^t)^a\! =\! g^{at} & & & \xleftarrow{B} &  s= T^b = g^{bt}
  &  &  \\
 &  &\! s_{TB}\! =\! B^t\! =\! (g^b)^t\! =\! g^{bt}\! \\
\end{array}
Now, it is clear that $s \neq s'$ and MITM can listen to the communications by using the keys decrypt, read, encrypt, and transfer, more. This can be detected by fingerprinting or prevented by digital signatures as in TLS.
The Telegram Backdoor (Fixed in 2013)
Alice and Bob agree on the modulus  $p$ and a base $g$
\begin{array}{lcccl}
\text{Alice} & \text{Trans} & \text{Telegram} & \text{Trans} & \text{Bob}\\ \hline
a \stackrel{R}{\leftarrow} \mathbb{Z_p}, A = g^a&   & & &b \stackrel{R}{\leftarrow} \mathbb{Z_p},B = g^b\\
  & \xrightarrow{A} & t  \stackrel{R}{\leftarrow} \mathbb{Z_p}, T = g^t & \xleftarrow{B,nB} & nB \stackrel{R}{\leftarrow} \mathbb{Z_p}\\
  & &  & \xrightarrow{T} &  \\
 &  &  nA = A^t \oplus B^t \oplus nB & &  \\
 & \xleftarrow{T,nA} &  & & & \\
s' = T^a \oplus nA &  &  & & s= T^b \oplus nB\\
\end{array}
Where the $nA$ is the nonce of Alice and $nB$ is the nonce of Bob.
Now we can see that $s = s'$ since $s = T^b \oplus nB = g^{bt} \oplus nB$ and
\begin{align}
s' &= T^a \oplus nA \\
   &= g^{ta} \oplus A^t \oplus B^t \oplus nB\\
   &= g^{at} \oplus g^{at} \oplus g^{bt} \oplus nB\\
   &= g^{bt} \oplus nB \\
   &= s
\end{align}
Therefore the fingerprinting will not work to detect the MITM attack, however, The server has already information to listen to the communication or more.

Are there any other examples of DHKE backdoors?


texts: Old French Cipher w/ Text Hidden In Drawing

texts:
I'm trying to find a cipher challenge I saw a few years back, it was an old drawing (I think 1800's or earlier) with clouds and stars on it and French text was hidden in the image.

Does anyone happen to know the name of this drawing/cipher I'm talking about?


texts: Help understanding syntax used in security proof

texts: I am looking through this paper and am trying to understand the proofs better. One of the theorems the authors are proving (Theorem 5.1) contains syntax of Adv followed by "cdh" in the superscript and some values as parameters within parentheses after. I've posted an image of the theorem in question for convenience. What does this syntax mean and what do the parameters for it mean?


texts: Raw signature of public key vs full certificate

texts: I'm working on an device that will have its own keypair to sign data that it acquires. The public key will be signed with a provisioning key to ensure authenticity of the device. I want to put the public key in a QR code printed on the device, as well as the signature by the provisioning key. If I use a regular X509 certificate structure the barcode gets really huge. Are there any pitfalls or really good reasons not to just put the public key and signature - base64 encoded - instead?


texts: Paillier encryption: Many private keys for a public key

texts:
Assume $N$ is a public key for paillier encryption, generated by a third party.

Question: Given $N$ can each client generate its own private key, such that its public key is $N$? So all parties separately generate their private key, but their public key is the same.


texts: Is perfect forward secrecy (PFS) possible without public key cryptography

texts: I have an understanding of PFS as used in most key agreement algorithms as well as things like TextSecure protocol and ratchets. My undestanding is that PFS is not possible without asymmetric (public key) cryptography. Am I missing something? Can PFS be achieved with symmetric cryptography and preshared keys only.


texts: Is there a standard method to compare hardware-implemented ciphers?

texts:
I have been reviewing literature and I am trying to determine the best method to compare ciphers in hardware.  The two methods that seem to be somewhat de facto standard the literature are looking at throughput for a 100kHz clock, and looking at area in GE (gate equivalents).  I take issue with these methods because for the clock method, the initial state is not given, ie: I do not know if this is measured from a loaded state.  The second method I have an issue with because GE is the area of a NAND gate, and if you use a huge NAND, you look like your implementation is relatively better.

Is there a standardized method to compare ciphers on a hardware level that is not this seemingly de facto method?

Furthermore, is there a standard method to compare Feistel ciphers against a substitution-permutation network?

If someone could point me to a document that outlines a method to compare ciphers from the implementation standpoint, it would be helpful.


texts: Problem with e-cash system with multiple banks

texts:
Say that many banks issue electronic cash of a particular type.

If there is a malicious bank and user collusion, the malicious bank signs electronic cash for a particular user. This user then takes the electronic cash to other banks to withdraw money. This way the malicious bank can get a large amount of cash from other banks.

Can such a multi-bank electronic cash system be established only if it all banks do not act maliciously?

Related multi-bank electronic cash papers:
Fair Electronic Cash Systems with Multiple Banks

A New Certificateless Electronic Cash Scheme with Multiple Banks Based on Group Signatures


texts:
Devise a scheme so that a message M can be shared among X, Y and Z in such a say that the only way of recovering the message is when X is present with either Y or Z. When X isn't present or each is alone, they will not be able to recover the shared secret.

Additionally, generalize the above to devise a scheme so that a M can be shared among 5 entities such that the only way of recovering the secret is when either X and Y are both present or when C, D, E are all present together.

I have no idea how to create a hierarchy such as what is being proposed. Any ideas?


texts: Decryption of a file encrypted by pseudo-random number generator (The Linear Congruence rand()

texts:
How to decrypt this file:

https://drive.google.com/open?id=1gZCujDYmEL-FZ5o_xBUS-Ng5979HSsZ7

Given that the only information available about it are:

It has been created on 21/3/2018, 9:05:15 AM
The plaintext of the file is probably starting with "\documentclass[12pt]{article}", and it's a latex file
The code used for encryption is in C, and used a pseudo-random number generator (The Linear Congruence rand()):

/* The ISO/IEC 9899:1990 edition of the C standard */
#define RAND_MAX 32767
static unsigned long int next = 1;
int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}
void srand(unsigned int seed)
{
    next = seed;
}

#include <stdio.h>
#include <time.h>

//Return a byte at a time of the rand() keystream
 char randchar() {
  static int key;
  static int i = 0;

  i = i % 4;
  if (i == 0) key = rand();
  return ((char *)(&key))[i++];
}

int main(int argc, const char* argv[]) {
  static char randstate[64];

  srand(time(NULL));
  FILE *input, *output;
  input = fopen("Homework1b.tex", "r");
  output = fopen("Homework1b.tex.enc", "w");

  int c,rc;
  while ((c = fgetc(input)) != EOF) {
    rc=randchar();
    printf("c=%d (%c) and rc=%d\n",c,c,rc);
    fputc(c^rc,output);
  }
  fclose(input);
  fclose(output);
}

I read about the weakness of C random and I know that knowing a part of the plaintext should help, but couldn't figure it out.


texts: Is $f\colon x\mapsto g(x+1)$ necessarily a pseudorandom function?

texts:
Let $l\in\mathbb N$ and suppose
$$g\colon\;\{0,1\}^l\to\{0,1\}^l$$
is a pseudorandom function.
Is $f$, defined as below, necessarily a pseudorandom function as well?

$$f(x)=g((x+1)\bmod2^l)$$


texts: Proving G(x)=x||[x^2 mod 2^N] is not a PRG

texts:
This was a question from my exam yesterday.
We have that $G:\{0, 1\}^n\rightarrow \{0, 1\}^{2n}$ and
$$G(x)=x\mathbin\|[x^2 \bmod 2^n]$$ with $x$ is uniform and $|x|=n$, give an efficient distinguisher $D(w)$ that shows that $G(x)$ is not a PRG.
After writing a program that shows all values $[x^2 \bmod 2^n]$ can take for some fixed $n$, I found that there is a mirror pattern in these values, but I don't see how to mathematically prove this.


texts: How do I create a PKCS#7 or CMS SignedData in python?

texts:
There doesn't appear to be PKCS#7 or CMS support in pyCrypto. I'd appreciate a recommendation on a Python library wth CMS / PKCS#7 support. Ideally, there will be a call that will create return SignedData given a signer certificate, an RSA private key and a payload (File or byte array) to sign.

I've looked at pycrypto-PKCS7 and as best as I am able to tell it only verifys signatures.

Your help / insights are greatly appreciated.


texts: Any algorithm with a pair of master keys and multiple pairs of subkey for a secure key escrow?

texts:
Note: This question looks like my other question — Any algorithm with a master key for decrypting private key encrypted messages? — which is perfectly answered by @real-or-random, but this one is different in how subkeys are generated.

Assume the following:

Create a pair of master private/public key
Create a private/public subkey #1 based on the master public key
Create a private/public subkey #2 based on the master public key
Encrypt data #1 with public subkey #1
Encrypt data #2 with public subkey #2
Possible to decrypt data #1 with both private subkey #1 and master private key
Possible to decrypt data #2 with both private subkey #2 and master private key
Impossible to decrypt data #1 with private subkey #2
Impossible to decrypt data #2 with private subkey #1

Is there any algorithm out there that implements the above scenario?


texts: How much does using the same $H$ for all messages weaken GCM?

texts: How much is GCM weakened by using the same MAC key $H = E_K(0^*)$ for all messages that use the same key (which is what GCM actually does) instead of using $E_K(N||0_{32})$ (which is different for each message)?


texts: Using cryptography to protect database integrity

texts:
I'm designing a micro-services system where each service manages some set of entities (User, Account, e.g).

I want to be able to verify the authenticity of entity identifiers (e.g User-Id and Account-Id), to make sure the identifier was actually produced by service and not some random data a user produced.

For example, the Account-Service has a Create-Account method that accepts a User-Id (the owner of the account), I want to avoid going to the User-Service in order to check if the User-Id actually exist (or using database foreign keys). The identifiers are 64-bit integers.

Two additional requirements are for the cryptography algorithm is to be very fast and produce short as possible ciphertext/MAC. I don't care if the 64-bit identifiers would be exposed.

Authenticated encryption with sharing the secret between the services would produce a very long string and would be too slow.

I'm considering SipHash but I'm not sure if it is secure enough for this purpose, maybe the 128-bit version of SipHash?

Any other algorithm or method to achieve this?


texts: Attacking AES without transposition using ShiftRow and Mixcolumn layers

texts: How can we attack by using chosen plaintext attack (and which plaintext should we choose) if AES didnt have the ShiftRow and Mixcolumn layers. I know each byte would be independent in the 16 byte scheme but couldnt figure out a way to attack.


texts: Solving modular matrix equations via Gaussian elimination or System of linear equations (SIS assumption?)

texts:
Suppose $S \in \mathbb{Z}_q^{m \times m}$, and the norm of $S$ is less than an upper-bound $\beta$.
Additionally, $A_1, \cdots, A_k, C_1, \cdots, C_k \in \mathbb{Z}_q^{m \times n}$.
Here, $k \geq m>n$, and $q$ is a large prime.
And $S$ is unknown.
The following equations are satisfied
$SA_1 = C_1$
$SA_2 = C_2$
$\vdots$
$SA_k = C_k$
Can I solve this problem by using Gaussian elimination or any method of system of linear equations?
Note that I think this problem is similar with the lattice hard assumption - SIS.
I am not sure whether this problem has a solution.


texts: How can Whatsapp identify forwarded attachments

texts:
Sometimes Whatsapp shows that an attachment was often forwarded.
How do they know this if the message is end-to-end encrypted?
Even with hybrid encryption I encrypt with my key and store my attachment on the server.
So do they hash the attachment in the client and store the hash? So they would know what attachments I forwarded and when?


texts:
I want to know how security of DGHV can be breached using oracle and Binary GCD. As I study this paper : Fully Homomorphic Encryption over the Integers But I am not able to understand Section 4.1:

  Theorem 4.2.
  Fix the parameters (ρ, ρ′, η, γ, τ) as in the Somewhat Homomorphic Scheme from Section 3 (all polynomial in the security parameter λ).

  Any attack A with advantage ε on the encryption scheme can be converted into an algorithm B for solving ( ρ, η, γ ) -approximate-gcd with success probability at least ε/2. The running time of B is polynomial in the running time of A, and in λ and 1/ǫ.

I also can't understand the Subroutine Learn-LSB(z,pk) and the Binary GCD following it.


texts: Is there any more asymetric-time permutation than x^3 (mod p)?

texts:
I've been using "asymetric-time bijective functions (or permutations)" for several practical uses. I've applied them to solve problems in software-attestation and proof of unique blockchain storage.

An asymmetric-time permutation is basically a public permutation F that takes a lot of time to perform in one direction (expensive direction) and very short time in the inverse direction (cheap direction). The most interesting property of an a-t permutation is the asymmetry ratio, which is the (average) ratio between expensive and cheap computation times.

This is a practical construction that is evaluated both ways in a protocol so the expensive computation must not be unfeasible: it may take 1 second of computation for a target CPU. Generally the expensive direction time is chosen so that is takes more than the time a response must be sent by a prover in an interactive challenge-response protocol.

One of the best a-t permutations I found is $f^{-1}(x)= x^3 (\bmod p)$, where $p$ is a large prime. The ratio is $O(n)$, where $n$ is the number of bits in $p$.

Another desired property is that you cannot break F by pre-computing and then turn expensive evaluations into cheap ones. So the domain size must be $> 2^{64}$.

The a-t function may have other desired properties, such as the ability to probabilistically test if $f^{-1}(x) = y$, given only a part of $x$ chosen by the challenger.

Are there other a-t functions with comparable or higher asymmetry ratios?

Candidates may be a trapdoor function such that the trapdoor is unknown and no third-party trust is required (nothing up my sleeve number). In other words, the verification logic must be public, and not limited to the challenger.

Note: I think I'm the first to specifically focus on a-t functions and its practical applications, but let me know if you find any prior mention.


texts: How to anonymously transfer ownership where sender cannot resend

texts:
I'm new to cyptography, so I apologize if this is a dumb/impossible goal or has already been answered (I was not able to find it by searching).

I wish to devise an anonymous protocol for transferring digital goods, where the message contents are publicly viewable, but neither sender nor recipient can be determined from the message contents alone.

Additionally, once the sender has transferred the goods to the recipient, he should not have the ability to resend the same goods again to another recipient.  Only the initial recipient should have that ability (i.e. a recipient should obtain sole ownership of the goods once transferred).

The goods may change hands many times, and ownership should be publicly provable at the time of a transfer without revealing the identity of the sender or recipient.

My initial design is for all users in the system to generate their own public/ private keys and a transport (for Diffie-Hellman exchanges).  A user's public identity would consist of their public key and transport.

When a sender wants to transfer goods, he first generates new random public/ private keys and transport (not his publicly known values, in order to obscure the fact that he is the sender).  He uses these in a Diffie-Hellman exchange with the recipient's publicly known values to generate a shared secret.  This shared secret is used as a salt to generate a specific public/private key pair.  The sender also generates a completely random public/private key pair.

The sender uses the specific public key to encrypt the random private key.  This encrypted value is included in the message contents, along with both public keys and the generated transport.  The message contents also contain a random number, and that number encrypted with the specific public key.

The sender also adds the hash of a previous message which was used to transfer ownership of the goods to him originally.  The sender then signs the message using the private key that was encrypted in that previous message.

Users in the network listen to messages, and attempt to recreate the shared secret from the public key and transport included in each message, using it as a salt to recreate the specific public/private key pairs.  If the specific private key decrypts the correct random number, then a user comes to know that he is the intended recipient.  He can then use the specific private key to decrypt the random private key, which he can now use to prove he has ownership of the goods.

The problem with this strategy of course, is that both the sender and recipient have access to the key used to prove ownership, and this would allow the sender to transfer the goods to additional recipients (i.e. the original recipient does not have sole ownership of the goods).  Are there some additional cryptographic measures that could be added to this process to prevent the original sender from re-sending the goods?  Or am I heading down a dead-end path and need a better strategy?


texts: FHE: What is the difference between multiplicative depth and multiplicative level?

texts:
I have seen the terms multiplicative depth and multiplicative level while reading

Faster homomorphic encryption is not enough: improved heuristic for multiplicative depth minimization of Boolean circuits by Aubry et. al, 2019.

Is there a difference between the term multiplicative depth and multiplicative level?


texts: How do you calculate the linear approximation of an S-BOX?

texts: I've been following this very good tutorial on linear cryptanalysis, and I'm stuck at the linear approximation part. I have no idea what input and output masks are. I don't understand what he's doing and why. Can somebody please help?


texts:
In case I am using CBC cipher in that case is it must that my encrypted text is in multiple of the BLOCK SIZE?
Is the same true for GCM?


texts:
I am following a document here about CTR mode of encryption. I have some point uncleared.
At the part 1 Review of Counter-Mode Encryption.
Operation.

  To encrypt using CTR-mode encryption, one starts with a plaintext  M
  (an arbitrary bit string), a key K, and a counter ctr , where ctr is
  an n-bit string.  Let C be the XOR (excusive-or) of M and the first
  |M| bits of the pad  EK(ctr) || EK(ctr+1) || EK(ctr+2)... The
  ciphertext is(ctr,C), or more generally, C together with something
  adequate to recover ctr.

  To decrypt ciphertext (ctr;C) compute the plaintext M as the XOR  of C
  and the first |C| bits of the pad  EK(ctr) || EK(ctr+1) ||
  EK(ctr+2)...

  Therefore, decryption is the same as encryption with M and C
  interchanged

As I think, the pseudo code will be:

selectFirst(pad, plainText M){
    int n = length(M);
    return n first element of pad
    return firstElements(pad, n);
}

void ctr(){
    string M;
    key[16] K;
    n-bit-string ctr;
    pad = EK(ctr) || EK(ctr+1) || EK(ctr+2)...
    firstM = selectFirst(pad, M);
    C = xor(M, firstM);
}

EK (x) is encrypt x (using some algorithm such as AES) with key K.
But I don't understand:

  what is ctr + 1, ctr+2...?
  Is EK(ctr) || EK(ctr+1) || EK(ctr+2)... an 'OR' operation? and what is its result?
  Is CTR mode one-time execution and not using loop?


texts:
I am looking to implement Ed25519 for decentralized identity at scale.

Has Ed25519 has gone through rigorous cryptanalysis?

Could there be a backdoor in the algorithm?


texts: How is a fake private key used in CloudHSM?

texts:
I've noticed that AWS CloudHSM uses an openssl command to generate a fake private key for web servers that offloads cryptographic functions to a CloudHSM. How does this key work? And what purpose does it serve?

As an example from the AWS CloudHSM docs:

Generate a fake private key using:

openssl genrsa -engine cloudhsm -out <web_server_fake_PEM.key> 2048


texts: A name for “word fingerprints” (technique for breaking monoalphabetic substitutional ciphers)

texts:
I have invented a technique for breaking monoalphabetic substitution ciphers. However, I believe that such simple thing must have been already invented. I wonder how is this called. I call it “word fingerprints”.

I assume that ciphertext is a natural language, you can identify words (e.g., you have guessed what character is space by its frequention, or spaces aren't encrypted at all), but you have limited or no knowledge of other symbols. I also assume you have an idea about the language dictionary.

Then, you can just pick a word and learn something about it not only by its length, but also by information what characters are the same and what characters differ.

In order to perform it more systematically, I suggest a canonical form of an unknown word, called word fingerprint: All occurrences of the first unique character is replaced by the first letter of alphabet (say “a”), all occurrences of the second unique character is replaced by second character of a alphabet (say “b”) and so on. In other words, going letter-by-letter, you substitute the letter by the same letter you have already substituted it, or (if you see the letter the first time), you substitute it by first unused letter of the alphabet. (If the description is unclear, I can provide pseudocode.) For example:

“hello“ –> “abccd”
“hell” –> “abcc”
“help” –> “abcd”
“alphabet” –> “abcdaefg”
“unique” –> “abcdae”

Due to nature of monoalphabetic substitutional ciphers, word fingerprint is the same for plaintext word and ciphertext word (regardless of the key). While fingerprints are generally ambiguous, a single long word is likely to have an unambiguous fingerprint. Once you know some mappings of the key, you can disambiguate more fingerprints.

But back to the question: Is there an established name for word fingerprints or any similar concept? I prefer using established terms.


texts: How could consumer level OTP + QKD over the internet ever be practical?

texts:
Please note, I am in no way questioning the future usefulness of quantum key distribution (QKD) in certain applications. I have no doubt it will prove useful for large banks, and in certain military research applications.

However, I cannot ever see it becoming common at the consumer level, or even enterprise level, even if the cost of sensitive quantum hardware decreases drastically.

http://users.telenet.be/d.rijmenants/en/onetimepad.htm

  One-time pad encryption nevertheless has a bright future. It is in fact the only crypto algorithm that has any future. Once that computational power and codebreaking technology has surpassed the capabilities of cryptologists and the limitations of mathematics to make strong encryption, there will no longer be any crypto algorithm that survives the evolution of cryptology, unless it meets the standards of information-theoretical perfect security.

The above article claims that all other encryption algorithms will be made obsolete by computing advances, and therefore, we must at some point move to a combination of One Time Pad (OTP) and QKD. I find this claim to be dubious, but as a non-cryptography expert, I am trying to keep an open mind.

Although this article is mostly about OTP, QKD would need to be used along side OTP to be of much practical value for all but a few select applications.

My doubts stem from QKD not seeming compatible with the principals and implementation of the world wide web. The WWW requires decentralized routing; that is to say, the electrons you receive, will never be the actual electrons I sent you, and that is okay, as long their frequency pattern matches.

To my knowledge, there is no way to duplicate a photon's properties without collapsing its wave function; perhaps this assumption is incorrect?  That means, my server would have to find a way to redirect the same photon to its intended target, which seems error prone and unpractical.

Even if we can find a way to duplicate a photon (or electron) without collapsing its wave function in an efficient manner, how do I now transmit that wave function over wifi, which is how most people use the internet?

Am I misunderstanding something here that would allow widespread QKD and OTP to become practical for a large distributed consumer network? Or is the conclusion this article came to questionable as I suspected?


texts: What's the entropy of the output for Tiger Encryption?

texts: I'm tasked to apply tiger encryption to my string(key). Does anyone have any idea how to find the entropy of the hex output by tiger encryption?


texts: Does signing multiple messages with the same RSA key weaken the encryption?

texts:
Here is the scenario,

I am signing roughly 1000 messages, which consist of 16 byte hashes, with 1024 bit RSA.
The private key is only used to sign the hashes, and there is no padding scheme.

The attacker has access to all 1000 messages and the public key. That is all they have to work with (no chosen plaintext ability, etc).

Does access to a large number of signed messages make it easier for the attacker to create a valid signature for a hash of their choosing?

If so, how? And would a padding scheme protect against it?


texts: Orthogonal generators of a group in Lelantus protocol

texts:
In the Lelantus Paper, the authors mentionned this:

  In our case, the commitment key ck specifies a prime-order group G and three orthogonal group generators $g, h_1$ and $h_2$.

G is mentioned in the performance section of the paper to be the famous elliptic curve secp256k1. Hence, I don't understand the notion of "group generators" that are orthogonal.

Indeed the group G is of prime-order and obviously commutative (even in the general case). Hence, non-trivial generators are of prime order p as well, and their generated subgroups are the whole group G.

Am I missing something here or is the "orthogonal" notion useless or even wrong?

Note: For me, it would make sense if the sentence meant that $\langle g,\ h_1,\ h_2\rangle\ = \ G$ and the subgroups $\langle g\rangle, \langle h_1\rangle, \langle h_2\rangle$ have trivial intersections together, but the prime order of the group $G$ forbids that, no?


texts: How to determine the concrete security of lattice cryptosystems?

texts:
I am currently reading about lattice cryptography and am interested in the cryptosystems based on the LWE problem. I understand the reductions from lattice problems to dLWE. Then we base our belief in the cryptosystem (say Regev or dual Regev PKC) on dLWE. But this is however asymptotic. From what I understand, the way this works is we believe breaking SIVP or whatever lattice problem takes time a very large function of n, and from the reduction we get a SIVP solver, so any algorithm which breaks the cryptosystem also is necessarily is a very large function of n.

What I don't understand however is how does one give parameters to these cryptosystems (for example, if I want 128 bits of security, how large should the LWE instance be)? I have read a couple of papers on this topic and have not really understood it. My comprehension is that we solve LWE like an instance of BDD. But these papers discuss basis reduction and ways of solving SVP and I do not know how to link these things together.

Sorry, my English is really bad.


texts: is OPE able to produce different cyphertext for same plaintext?

texts:
Given a plaintext p, is OPE (Boldyreva et al.) able to produce n different cyphertext c1...cn for the n occurrences of p?
If not, there exists an order-preserving encryption scheme able to do that?


texts: I have $N$ users, all of them creating a group digital signature. Also I have user $A$. How can I check if user a signed or not signet in this signature? Is it possible ? Are there other methods how I can check if user $A$ is one of the group $N$?


texts: Secret sharing by using just "private secrets"?

texts: TLS is using 3 way handshake. Isn't that possible to use such 3 way handshake protocol to share a secret without using a public key scheme, for instance as follows: Let A, B be private secrets of Alice and Bob respectively, where A,B  are elements in a commutative groups. Alice wants to share the secret X with Bob, and sends Bob AX. Bob multiplies it by his secret B to create BAX, and sends it back to Alice, that Multiplied it By 1/A, creating BX, that is sent back to Bob, that multiplies it by 1/B, getting X, the secret Alice wanted to share. Is there a principle problem with this scheme?


texts:
I am planning to use Argon2 in my Android app to encrypt some sensitive info that is only stored on the user's phone (in an SQLite DB) and not exported anywhere else. From documentation I see that Argon2d is more resistant to GPU based brute-force attacks compared to side-channel attack in 2i.

Would this mean that in my scenario, it'd be better to use the 2d implementation? Since, in "usual" scenarios it is apparently recommended to use 2i.

Finally, is Argon2 studied sufficiently enough, or should I choose the Android natively supported PBKDF2 with HMACSHA1. I can reasonably use 20,000 iterations in the latter.

Basically, I want to delay malpractice/protect user's data from being decrypted through brute-force methods. I do understand that it also depends on the user's password input.


texts: What type of encryption is this homebrew "encyption algorithm"? ${}$

texts:
Background:
Quite a long time ago (somewhere 1998) I thought I was really clever and invented my own encryption/decryption code. Looking through old code I rediscovered my old algorithm. (No, it was never used in any production environment.)

I'm wondering what type of encryption my naive self invented back then. I'm guessing it is a polyalphabetic substitution cipher, but I'm not really sure?

My Questions:

What type of algorithm is this?
How weak is it against modern day cryptanalysis and what methods would be used to break it?

What the code below does:
The algorithm encrypts and decrypts based on a set 64 alphabets. Each alphabet consists of the same 64 characters in random order; each character is included exactly once per alphabet. This set of alphabets is effectively the key for the algorithm.

To start, the plaintext is base64 encoded. Then each individual character, in the base64 encoded plaintext, is substituted by a character from one of the alphabets. The first characters is (always) picked form the first alphabet, for subsequent characters the alphabet is selected based on the index-number of the substituted value of the character preceding it. So, it 'encrypts' one character at the time and, if one character in the ciphertext changes, the decryption will (most likely) be garbled from that point on.

The code also adds base64 style padding to the ciphertext, in an attempt to be 'even more secure' by passing of the ciphertext like regular base64 encoded data.

The Algorithm:

Encryption is being carried out over letters from a 64-element alphabet in the following mode:

$$C_0=F_0(P_0)\quad C_i=F_{C_{i-1}}(P_i)$$

Where $F:\mathbb Z_{64}\times \mathbb Z_{64}\to\mathbb Z_{64}$ represents 64 different, random, fixed permutations forming the key.

Reference PHP-Code can be found in the revision history.


texts: Is multiplicative secret sharing secure?

texts:
I suggested mulitiplicative secret sharing in an answer to another question, but noted that I wasn't sure if it was even secure and was hoping someone would comment on the security. Since no one did, I thought I'd ask it as a separate question.

Fix a multiplicative group, say $\mathbb{Z}_p^*$.

To share $s$ with $k$ parties such that all $k$ are required to reconstruct $s$, we choose $s_1,s_2,\dots,s_{k-1}\in\mathbb{Z}_p^*$ at random and set $s_k=s*(s_1*s_2*\dots*s_{k-1})^{-1}$. Thus, $s=s_1*s_2*\dots*s_{k}$.

What is the security of this secret sharing method? Is it information-theoretic? In other words, if fewer than $k$ parties get to gether they should (either for a computationally bounded or possibly an unbounded adversary) learn no additional information about $s$.


texts:
I'm new to MPC. I was reading about it when I found an example that seemed to be trivial about how it works.

In the picture below, the way X1 sends its data to X2 is by generating a huge random number, add its number to it, and send this to X2. X2 will do the same by adding its value to what it has received, and then send that to X3, and so on.

This does not look secure to me. Isn't the direct addition trivial?


texts: What is the difference between subtracting the modulus from a scalar field element and reducing it?

texts:
When implementing a Field element, we define the necessary operations on the data structure.

One function that I see is a "scalar reduce" function, which effectively reduces a random scalar so that it is in the scalar field.

What is the difference between this and subtracting the modulus from such number?

Example:

Let a be a scalar chosen at random
Let q be the modulus

I have seen code that does the following:

if a > q{
  a = q-a
}

Why did it not try to reduce a by doing the modulus?


texts: Hashing list: concatenation vs prepending

texts:
In Schnorr's NIZK proof there is an interesting remark:

  Within the hash function, there must be a clear boundary between any
  two concatenated items. It is RECOMMENDED that one should always
  prepend each item with a 4-byte integer that represents the byte
  length of that item.

I know, that it's generally a good practice for preventing length-extension attacks.
But, look closely at the challenge:

  $c = H(g \Vert V \Vert A \Vert \mathsf{UserID} \Vert \mathsf{OtherInfo})$

$A$ is a valid public key ->  fixed length

$g$  is a a generator -> fixed length

Suppose both $\mathsf{UserID}$ & $\mathsf{OtherInfo}$ have fixed length as well.

It seems that in this particular case, Plain concatenation can be safe because all but one of the inputs have a fixed length.

Is it so? How vulnerable is Plain concatenation when all (or all but one) inputs have a fixed length compared to Prepending the length?


texts: TCG design specification of TPM and nonce creation

texts:
I am reading TPM Main Part 1 Design Principles (PDF) which states:

  The creation of all nonce values MUST use the next $n$ bits from the TPM RNG.

I do not know what this means, or how to find out what it means. What is “the next $n$ bits”?  There is no other comment or hint on this section which might explain $n$
.


texts:
For a scheme to be at least CPA secure, one has to randomize the scheme. In case of a secret key encryption scheme, the used randomness will typically become part of the cipher text as in the case of an IV and is "public" (This is not a necessary requirement but how most algorithms work).

Now, if I switch to public key encryption schemes, the randomness will typically not be "public". The decryption algorithm simply removes it without necessarily really knowing it, like for example in the case of LWE or McEliece.

Now my question is: Is this a necessary requirement for public key encryption schemes that at least some of the randomness is not explicitly given as part of the cipher text?

Moreover, might it even be the case that all randomness that effects security has to be non-public? To be more precise, does all randomness that I cannot replace with a public constant value, without harming the security of the scheme have to be private.

(As a motivating example of randomness that can not effect security: I can always add randomness by first XORing the plaintext with a random bit string and adding this bit string to the cipher text but the scheme would be as secure as if I XORed the all zero string instead. Hence, this randomness could be omitted without harming the security.)


texts:
In the book Serious Cryptography
It says for a cipher's permutation to be secure
"Different keys should result in different permutations. Otherwise it becomes easier to decrypt without the key: if different keys result in identical permutations, that means there are fewer distinct keys than distinct permutations, and therefore fewer possibilities to try when decrypting without the key. In the Vigenere cipher, each letter from the key determines a substitution; there are 26 distinct letters, and as many distinct permutations."
Cam someone explain this please?


texts: Where did ChaCha20 and Salsa20 stream ciphers get their names from?

texts:
This is not a question targeted at a specific crypto implementation, but a question out of curiosity. What's the reason for calling the stream ciphers ChaCha/Salsa?

I couldn't find any information about this on the Internet. Are those names somehow related to their internal structure, or just to make them stand out from all the other ciphers out there? For example, AES used to be called the Rijndael Cipher (derived from the names of its creators), before NIST standardized it.


texts: Checking the integrity of RSA public key

texts:
Let's say I need to verify a digital signature and the public key is stored in untrusted storage which I need to fetch before I verify the digital signature. However, I can store the cryptographic hash of the public key in trusted storage and I decide to use the hash to verify the integrity of the public key. Now say I am using RSA PKCS #1 1.5 signature scheme, the public key contains (n, e), i.e., modulus and public exponent.

Here is the questions:
Can I compute the only hash of the modulus for integrity? Do I get any security advantage if I compute the hash of the modulus concatenate with the public exponent? Specifically, I wonder what could go wrong if the attacker can change the my public exponent? (Assume the signature is created with public exponent 65537)


texts: Timing vulnerability of byte array equality test?

texts:
Would the following code to test MAC equality leak timing information ?

bool equal(unsigned char *a, unsigned char *b, int len) {
    unsigned char c = 0;
    for (int i = 0; i < len; i++) {
        c |= a[i] ^ b[i];
    }
    return c == 0;
}

More precisely, does the last expression c == 0leak timing
information ?

I don't think so, because it doesn't allow to know where would be the mismatch.

Why are then some crypto libraries using complex expression to convert c into a 1 or 0 value than later simply compare that value with a simple == with 1 (or 0) ?

Would a timing difference between MAC mismatch and identical MAC condition be relevant ?


texts: Is there a way to break this encryption?

texts:
I was wondering about making up a simple system to encrypt a file:

seed the random number generator with the passcode
generate as many random bits as the file has
xor

This has a vulnerability that if you encrypt two file A and B with the same passcode, xoring the two encrypted files would give the xor of A and B... so

seed the random number generator with the passcode concatenated with a hash of the file
generate as many random bits as the file has
xor

I think this fixes that vulnerability but a MITM could still flip certain bits inside the file by flipping bits on the encrypted file, so

seed the random number generator with the passcode concatenated with a hash of the file
randomly permute the plaintext in blocks of 128 bits
generate as many random bits as the file has
xor

I couldn't think of any vulnerability this system has. Do you know of any?


texts: Can we use higher strength SHA along with lower strength RSA key in SSL?

texts:
I have noticed when the RSA public key is 2048 bit, SHA-256 bit used for signatures. When the key is 3072 bit, SHA-384 bit used.  When the key is 4096 bit, SHA-512 bit used.

I have tried the following commands.

openssl genrsa -out my.key 2048
openssl req -new -sha512 -key my.key -out my.csr

It worked without any errors.

My question is that, will there be any issues when the SHA-512 is used with 2048 bit?


texts: Can we use HMQV in an asynchronous setting?

texts:
Following the HMQV paper, to perform a key-exchange, Alice ($\hat{A}$) and Bob ($\hat{B}$) perform the following:

$\hat{A}$ generates the long-term key pair ($sk_A= a$, $pk_A =g^a$) and the ephemeral key pair ($x, X=g^x$). Then $\hat{A}$ sends [$\hat{A},\hat{B}, X, \mathrm{sig}_\hat{A}(X,\hat{B})$]
to $\hat{B}$
$\hat{B}$ generates the long-term key pair ($sk_B= b$, $pk_B =g^b$) and the ephemeral key pair ($y, X=g^y$). Then $\hat{B}$ sends [$\hat{B},\hat{A}, Y, \mathrm{sig}_\hat{B}(Y,X,\hat{A})$]
to $\hat{B}$

Then both compute the session key $\sigma=g^{(x+da)(y+eb)}$ as $\sigma_\hat{A}=(YB^e)^{(x+da)}$ and $\sigma_\hat{B}=(XA^d)^{(y+eb)}$ respectively, with $d=\overline{H}(X,\hat{B})$ and $e=\overline{H}(Y,\hat{A})$

Following are my questions:

 if $X$ and $Y$ are pre-computed (before the key-exchange) and available on a TTP, can HMQV be used as an asynchronous key-exchange?
 In terms of performance, is HMQV better than X3DH? X3DH computes the session key as $\sigma=\mathrm{KDF}(g^{ay}||g^{bx}||g^{xy})$
 is $\sigma = (x+da)(y+eb)G$ the right transformation of HMQV final result in Elliptic curve cryptography?
 in the hash function $\overline{H}$, can we discard $\hat{A}$ and $\hat{B}$ without affecting the robustness of HMQV?