texts: How to prove correct decryption in Goldwasser-Micali cryptosystem

texts:
In How to prove correct decryption in Paillier cryptosystem, it was asked whether Alice (in sole possession of the secret key) can convince Bob that a given plaintext is the decryption of a ciphertext provided by Bob (who doesn't know its contents). In the case of Paillier encryption, the answer seems to be yes. Is anyone aware of a corresponding (preferably zero knowledge) solution to this problem in the case of Goldwasser-Micali encryption?
Thanks,
Neil.


texts: Support for hardware-accelerated crypto AES on ARMv8 processors running in 32-bit mode?

texts:
As I understand it, all ARM processors based on the 32/64-bit ARMv8-A architecture (and more recent iterations) support hardware-accelerated AES instructions.

Under Linux, the feature flags in /proc/cpuinfo are supposed to include aes for ARM processors which support these instruction (also pmull{2}, sha1, sha2 for other hardware crypto accelerations).

Many devices with ARMv8-A CPUs are nevertheless built with only 32-bit kernels and userspace, for example the very common Qualcomm MSM8916 / Snapdragon 410 platform.

I inspected /proc/cpuinfo on a rooted MSM8916-based Android device, and to my surprise the CPU is identified as ARMv7 — not ARMv8 — and the aes feature is not included:

# cat /proc/cpuinfo
processor   : 0
model name  : ARMv7 Processor rev 0 (v7l)
BogoMIPS    : 38.00
Features    : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt vfpd32 evtstrm
CPU implementer : 0x41
CPU architecture: 7
CPU variant : 0x0
CPU part    : 0xd03
CPU revision    : 0

processor   : 1
(same)

processor   : 2
(same)    processor : 3

processor   : 3
(same)

Hardware    : Qualcomm Technologies, Inc MSM8916
Revision    : 81b0
Serial      : 01d8fa2100000000
Processor   : ARMv7 Processor rev 0 (v7l)
Device      : harpia
Radio       : US
MSM Hardware    : MSM8916

Questions:

Is the kernel's lack of awareness of the aes feature bit a mistake, or limitation in the way that the kernel for this device has been built?
Is AES hardware acceleration truly not available when running on an ARMv8-A CPU running a kernel built for ARMv7?
Is it possible for userspace libraries or applications to take advantage of aes hardware support despite the fact that the kernel doesn't report its availability?


texts: What is the advantage of adversary if the random number repeats?

texts:
In proof of CPA-security of encryption scheme $(r, F_k(r)\oplus m )$
where:

$F_k$ is a keyed function
$r\in_R\{0,1\}^n$ is a random number,
on page 85 of Introduction to modern cryptography we have

The value $r^*$ is used when answering at least one of A’s encryption oracle queries: In this case, A may easily determine whether $m_0$ or $m_1$
was encrypted. This is so because if the encryption oracle ever returns
a ciphertext $\langle r^*,s \rangle$, si in response to a request to encrypt the message $m$,
the adversary learns that $f(r^*) = s\oplus m.$

My question is how can the adversary use $f(r^*)$?
Haven't we assume that the adversary doesn't know about $f$?

What I understand is that if we have used the keyed function $F_k$, then since the adversary doesn't know $k$, the knowledge of $F_k(r^*)$ can't be used because s/he still needs lots of time, that is $2^{|k|}$, to check which function $F_k$ where used. So it seems to me using the encryption scheme is secure even we repeat the random number $r$.
It seems that I am missing something but I can't find it.


texts: Solve a system of non linear equations over GF

texts:
I have the following set of equations:

$$M_{1}=\frac{y_1-y_0}{x_1-x_0}$$

$$M_{2}=\frac{y_2-y_0}{x_2-x_0}$$

$M_1, M_2,  x_1, y_1, x_2, y_2,$ are known and they are chosen from a $GF(2^m)$. I want to find  $x_0,y_0$

Does the previous set of equations is solvable?

And more...

If I have the following set of equations:

$$M_1=\frac{k_1-(y_0+(\frac{y_1-y_0}{x_1-x_0})(l_1-x_0))}{(l_1-x_0)(l_1-x_1)}$$

$$M_2=\frac{k_2-(y_0+(\frac{y_1-y_0}{x_1-x_0})(l_2-x_0))}{(l_2-x_0)(l_2-x_1)}$$

$$M_3=\frac{k_3-(y_0+(\frac{y_1-y_0}{x_1-x_0})(l_3-x_0))}{(l_3-x_0)(l_3-x_1)}$$

$$M_4=\frac{k_4-(y_0+(\frac{y_1-y_0}{x_1-x_0})(l_4-x_0))}{(l_4-x_0)(l_4-x_1)}$$

where $x_0,y_0 x_1,y_1$ are the unknown GF elements.

As Dilip Sarwate clarified the set of equations is constructed by someone who " chose three distinct x0,x1,x2, as well as y0,y1,y2, then computed M1, M2, and finally revealed $M_1,M_2,x_1,y_1,x_2,y_2$ but not $x_0,y_0$ to us" i.e. it is known that the system has solution.

My question was:
Can I recover the $x_0, y_0$ or in the second set of equations can I recover $x_0, x_1, y_0, y_1$ and generally in nonlinear sets to recover the respective $x_i, y_i$  by the provided info, on a GF? and the main point of my question: Does the fact that the set of equations is defined on a Galois Field impose any difficulties to find its solution?

I was not sure that it is possible to compute the solution of the  problem with the aforementioned parameters on a Galois Field.

As Dilip Sarwate stated in his answer the solution of the previous problem can be recovered for linear and nonlinear equations.


texts: Ensure Data Integrity In An ECDH Key Excange

texts:
Been playing around with the inner workings of onion routing and I have a problem. If I wanted to send the 2nd node of a relay network an ephemeral ECC public key, it has to go through node 1, so that node 2 does not know the IP of the client. Once the shared secret is calculated, an encrypted connection from the client to node 2 that essentially proxies through node 1 can be created, so node 1 can't view the info that passes through it from the client to node 2. However, how can node 2 be sure that the ephemeral ECC key it receives from the client via node 1 is the actual key. How can the integrity be verified, to counter MITM attacks?

I dont think that signing the key with a permanent ECC key would work because then the 2nd node would have to use the clients permanent ECC public key to verify the data, and then node 2 would know what the clients IP is, as it would have to be stored together, so that the correct key can be used to verify the signature.

How can the integrity of the key exchange be verifies without using digital signatures?


texts:
Are there any evidence (other than not being cracked so far) that the Bitcoin protocol is secure? "How secure" is it?

(I realize that this might not qualify as a meaningful question - feel free to edit if you can improve it. Also, if you liked this question, you might like the Bitcoin Proposal.)


texts: I am looking for a fast MAC (~few machine instructions) to be used for hash tables with 64-bit public inputs.  I can't use SipHash as the hash function will be inlined in too many places and so the code size of SipHash is too large.  The sole use of the MAC value will be in hash tables.  I want to avoid hash collision DoS.


texts:
on the NIST website for Message authentication There is a mention of 2 approved algorithms, i am curious about the first one. the link to FIPS 113, Computer Data Authentication appears to be dead since it redirects me to the homepage of NIST.gov

On a dutch Wikipedia article (the only wiki article i could find about FIPS 113, it is stated this FIPS is outdated and not secure by today's standards. Is this true? is the Algorithm described in FIPS no longer safe? would this make HMAC the only NIST approved MAC?

I have written an email notifying the NIST site administrator about the link.


texts: What are different components of Cryptanalysis. I can't seem to find them. Are they the same as Cryptosystem or is there any difference.


texts:
I was reading about the differences between block ciphers and stream ciphers. One thing that hit me was that stream ciphers like RC4 tend to be susceptible to bit-flipping attacks, in which flipping a bit in the ciphertext can predictably change the plaintext, allowing an attacker who knows the plaintext to change it in any way he/she wants, while in secure block ciphers, an attacker cannot flip a bit in the ciphertext and predictably change the block of plaintext.

How does Salsa20, being a widely used and secure stream cipher, protect against these attacks, if it does at all? If it doesn't, how does Salsa20-Poly1305 protect integrity of known plaintext?


texts: How are messages larger than 512 bits padded in SHA-256?

texts: In the NIST documentation for the Secure Hash Standard, it says to pad every message by appending the bit "1" to the end of the message, followed by k zero bits, where k is equal to the equation l (length of message in bits) + 1 + k = 448 mod 512. Then, it says to append a 64-bit block that is equal to the length expressed using a binary representation. The padded message should be a multiple of 512 bits. However, it does not seem to indicate how this would work for a message that is 512 bits or larger. My guess is that the equation above would be equal to the nearest multiple of 512 greater than the length minus 64. For example, for a message of 550 bits, k would be equal to 410. Am I right?


texts: Reusing encrypted message on MITM attack?

texts:
I'm using RSA public key private key for sending AES key from each client to server application.
then i'm using this AES key and IV for communicating between client and server.
what should i do for this MITM attack scenario??
client[encrypted text]   ---> Server
the MITM can use this encrypted text again to send it to server. consider if this encrypted text is an operation on transfering money.
the solutions i have planned for this are these:
1- attach new IV(encrypted) on each sending to server , so the server knows what's the next message iv is
well , i just can think about this only for now


texts: Example of calculating a primitive root for large prime?

texts:
I am trying to figure out how to calculate primitive root $w$ for a prime.
Following what I read, I generated my prime to be 'safe prime', $p=qr+1$.
I know $q$ (also prime) and $r$. Let's assume, for example: $q=11$, $r=8$ and $p=89$. Both $p$ and $q$ are prime, as needed.

I now find $w$ by choosing random number $h\mod p$ , take for example $h=41$:
$$w=h^r\mod p\\w=41^8\mod 89=32$$

However, $32$ is not a primitive root for $89$. I know I am probably get something wrong, please help me find my mistake.

Thank you for your time!


texts: Possible to determine the encryption key that was used by knowing the input and output of the encryption mechanism?

texts:
Assume that a malicious user knows what string is being encrypted (a user_id, for example, which the user can know) and can also see the result of the encryption (the encrypted user_id that is used to authenticate them to another site.)

If the user knows what is going into the encrypt function, as well as what is coming out, in theory it seems it could be possible for them to determine the encryption key as well.

Assuming that this is the case, what could be done to address this problem?

Background: The project I'm working on uses the code found below. I have concerns that the shared encryption key could become compromised http://grokbase.com/p/php/php-notes/1181cckm7e/note-105166-added-to-function-mcrypt-encrypt

The concern is simple: The key is shared, so if someone knows the key, they can trick the authentication mechanism and log in with whatever user ID they want.


texts: Why are the mixcolumns in AES in a fixed order? Can the order be changed?

texts:
Almost the same question as my “Why are the shiftrows in AES in a fixed order? Can the order be changed?” but this time it’s about the AES MixColumns.

Why are the mixcols fixed? Can we keep adequate security by changing the order? If not 'any' order, what about some other arrangements? Or is this arrangement the only one suitable?


texts: Known-plaintext attack on Blowfish in ECB mode

texts:
The protection scheme I faced recently seems so weak nowadays that a simple exhaustive key search would be enough to recover the user key in an acceptable amount of time (it's OK, since almost no practical benefit could be gained from knowing the plaintext), but I'm just curious whether the key recovery could be accomplished even faster and more intelligently.

The scheme consists of using Blowfish encryption with 40-bit key, with ECB mode of operation — i. e. no initialization vector, no feedback. This is countered by having a separate key for each document (or related set of documents), and by compression of documents.
On the other side, those documents are always ZIP archives with a single file packed in them, generally with the most simple capabilities. As a result, the first 32 bits (one Blowfish word) always contain the ZIP's local file header signature; the following 32 bits are usually constant for a given data producer, i. e. can be compared against a fixed value or can be verified partially. Further data is varying, but can be verified for plausibility as well.

The question is: does the knowledge an exact value of single block of plaintext give any advantage to key recovery — beyond the ability to easily check for a match in brute-force attack? Every discussion on that topic that I found claimed that Blowfish can't be reversed, but provided no proof for this; moreover, those topics were concerned about other modes than ECB and substantially longer keys. Then I started searching for discussions on recovery of subkeys instead of the original user-supplied key, and found this recent paper:

“All Subkeys Recovery Attack on Block Ciphers: Extending Meet-in-the-Middle Approach”, Takanori Isobe and Kyoji Shibutani, Sony Corporation
presentation of the same paper for Symposium On Applied Computing, 2012

The full paper seemed too general for me, with little explanation on used symbols. The only thing I understood is that for key length of 40 bits there should be more than one 64-bit block of known plaintext, which is not the case for me. The other bad thing is that I didn't notice anything about the round-wise subkeys (the P-array) there — they were talking about substitution boxes only. The last slides of presentation put me in even much more confusion, since they claim that subkey recovery attack is effective with keys longer than 292 bits.

PS. Regarding the speed of brute-force attack against Blowfish. My initial implementation in .Net performed about 2800 checks per second, reimplementation in pure C with heavy inlining raised the bar up to 27'500 in a single thread and about 200'000 in 10 threads on a Core i7-2600 with hyper-threading — that's just 64 days for a complete range scan. And, although Blowfish is believed to be GPU-unfriendly, an OpenCL bcrypt implementation shows even more performance, the more so that bcrypt is a heavier form of Blowfish.


texts: Compared to GCM or XTS modes, how secure is H xor R1, E (R2, R1, Message) for confidentiality and integrity?

texts:
Let R1 and R2 be (32 byte) random values, and let a H = Hash (R1, R2, Message) be of the same length as each R value.  Provided E (R2, R1, Message) is operating in some chaining mode, are there any known weaknesses of a scheme like this which aims to provide confidentiality and integrity?  The hash could also be an HMAC.

Basically, the following would be presented in succession:

(H xor R1), E (R2, R1, Message)

And verification would involve decrypting with the shared key to arrive at R1; xoring with the first part to arrive at a calculated H, and verifying that H agrees with the hash value that it should.  From that point onward only, further processing on the remainder of the message takes place.


texts:
I have an application written in C, running in Linux. It uses IPsec (ESP) (manually putting the IPSec packet together) to send certain packets. The algorithm used for encrypting the payload is 3DES-CBC (using Libgcrypt).

So my doubts are regarding the IV that I have to use. For this scheme to be secure:

Is it enough to generate a random IV?
If so, what random number generator source should I use for this? (e.g. /dev/random)

The other requirement that I noted while reading RFC 1851 is that the IV should be 64-bit long.

Update:

NIST Recommendations for Block Cipher Modes of Operations, Appendix C [PDF] states:

  There are two recommended methods for generating unpredictable IVs.
  The first method is to  apply the forward cipher function, under the
  same key that is used for the encryption of the  plaintext, to a
  nonce. The nonce must be a data block that is unique to each execution
  of the  encryption operation. For example, the nonce may be a counter,
  as described in Appendix B, or  a message number. The second method is
  to generate a random data block using a FIPS-approved random number
  generator.

Tried to find a list of all Linux random number generator implementations that are FIPS-approved but couldn't find much information on this.


texts: Learning to encrypt/encryption algorithms

texts:
I am a beginning programmer interested in coding an application of my own to encrypt sensitive files of mine. For example: lists of passwords, bank accounts, Credit Card numbers etc.

I was wondering what would be the easiest encryption algorithms to learn from a purely theoretical point of view?


texts: Ciphertext compression (Ring-LWE encryption and authentication system) after encryption?

texts:
Recently I came across an interesting looking cryptography article Ring-LWE Ciphertext Compression and Error Correction: Tools for Lightweight Post-Quantum Cryptography by Markku-Juhani O. Saarinen, which specifically state

  Ciphertext compression can significantly increase the probability of decryption errors.

Which I wonder now, does this indeed mean compressing the ciphertext, which I undertand isn't sensible (basically since encryption should randomize the output so it doesn't really compress after the operation) or doing the compression in the same go? Analogously to how AEAD does encryption and authentication.

I tried to gleanse something from the paper and read about this from the Internet, but being a rather layman on encryption methdos certainly doesn't help.


texts:
I've recently been reading an article about "using cryptography to store credentials", and I would love it someone explained this in more detail…

Up until Android 4.1, Android used a SecureRandom provider, that, given the same seed, after using setSeed(seed), it would generate the exact same stream of bytes. Because of this, people used this fact to generate AES keys for encrypting, only sharing the seed between users.

Google found out about this and introduced a new SecureRandom provider in 4.2 (based on OpenSSL's PRNG), which, for the same setSeed(seed) generates different outputs. They also recommend using PBE (PBKDF2 etc) for doing key generation, which is a fair recommendation (due to bruteforcing protection).

Why is sharing the seed and using SecureRandom "deterministically" so bad? Is it a bug?

This technique is even mentioned in the RFC1750

  It should be noted that if your technique for generating a sequence
         of key values is fast enough, it can trivially be used as the basis
         for a confidentiality system.  If two parties use the same sequence
         generating technique and start with the same seed material, they will
         generate identical sequences.  These could, for example, be xor'ed at
         one end with data being send, encrypting it, and xor'ed with this
         data as received, decrypting it due to the reversible properties of
         the xor operation.


texts: Is it possible to demonstrate that md5(x) != x for any x?

texts:
I am looking for an easy to follow explanation, if possible, that demonstrates/proves the validity (or not!) of this assertion:

for any X, md5(X) != X   (being X any string of 32 hex characters)


texts:
There are server programs and client programs.

Prepare two keys (A, B) for AES.
The A key creates an encryption table in advance with WhiteboxAes.
The B key creates a decryption table in advance with WhiteboxAes.
The client uses the A table, encrypts the data with WhiteboxAES, and sends it to the server.
The server decrypts and uses the data with the A key using the regular AES library.
The server encrypts the data using the B key using the regular AES library and sends it to the client.
The client uses B-tables in WhiteboxAES to decrypt and use the data.
In this way, I think the client is secure.

But what if:

Is WhiteboxAES meaningless and dangerous when using methods to generate encryption and decryption tables with one key and use them on the client?
For example, isn't it meaningless to use it for SaveData in a client program?


texts: I wrote my own cipher to encrypt messages. I would like to test a sample ciphered message to see how strong it is. Are there any tools for such task either in Windows or Linux ?


texts: Encrypting the same message using different schemes

texts:
$E_1$ and $E_2$ are IND-CPA secure encryption schemes.
$E$ is defined as:
$k_1,k_2 \leftarrow K_1 \times K_2$ .
$E_{k_1,k_2}(m) \leftarrow E_{1,k_1}(m)||E_{2,k_2}(m)$.

Hope the notations are in an obvious manner.
$\leftarrow$ means randomly choosing an element from the corresponding distribution. || stands for concatenation.

My question is whether the encryption scheme $E$ is IND-CPA secure.

Intuitively, this would be secure. If you can not get any information from either $E_1$ or $E_2$, should you get no information given both. (Of course there is a loophole here: $E_1$ or $E_2$ by itself may not leak information, however the combination of them may give some information away.)

When I tried to prove it I can not reduce the break of  $E$ to either $E_1$ or $E_2$. Neither can I find a counter example.


texts: Why isn't CTR mode (counter mode) used more often?

texts:
For the CTR mode, the design is good for parallelization, yes, it seems the benchmark of the program downloaded from crypto++ proves that on an Intel I7 CPU.

My question is that as most of CPU on the computers today are multicore and designed good for multithread calculation, why not all people use the CTR mode as it is much faster than the CFB mode (about 4 times faster on Intel I7-4770K, 3.5GHz CPU)?


texts: ECDSA over $\mathbb{F}_{p^n}$ for $n>1$. How to calculate $r$ and $s$

texts:
I'm having some trouble understanding how to calculate $r$ and $s$ as specified in the wikipedia page for ECDSA (https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm)

We can see on step 4 of the signature generation algorithm that they calculate the following:

$r = x_1 \text{mod}\ n$, where $n$ is the order of the group.

However, $x_1$ is an element of $F_{p^m}$, which for $m > 1$ it doesn't make sense to compute it's remainder over an integer.

Similarly on the next step they calculate $s = k^{-1} * (z + r d_A)\ \text{mod}\ n$. However, here I also do not understand what operation they are refering to when they write $z + r d_A$, since $z$ is a number and $rd_A$ is a curve point.

Surely I must be missing something very obvious but I cant figure out what. For $r$ it occurs to me that you could just take the modulus over the corresponding field element to $n$, since all the elements of $F_p$ are also in $F_{p^n}$.

For calculating $z + rd_A$ I'm at a loss though, how do you calculate the sum of an Integer and an element of $F_q$?


texts: Confused in selecting the encryption method for mobile number and email encryption

texts:
I'm new in cryptography and I'm developing a mobile app that gets user_name, E-mail ID, and mobile number as input. I'm a bit confused about how to encrypt that data so that I can decrypt it later.

Which is the secure way of encryption so that I can transmit the data to the server for storing. Suggest me some way on how to encrypt and send those data in encrypted form.


texts: The role of the dealer in visual cryptography

texts:
In visual cryptography schemes (VCS), there is special person called dealer. The dealer sets up the system, and the only one who knows about secret image. After encryption, the dealer distributes the shares to participants.

My question is, the dealer is one of $n$ participants or it should be from outside?


texts: Alternative way to provision secret in Intel SGX enclave

texts:
I have a case where I have multiple clients (non SGX, assumed safe) and server(SGX based), talking over a network. I wanted to provision a shared (per client) key which is used to encrypt and decrypt data.
The server admin is assumed to be an adversary. I do not want to use remote attestation as it will require every client to register for the IAS service and other sorts of things. Also, the server TLS connection terminates inside the enclave (used mbed-SGX). The client authentication is happening through username and password.
Now, I have few option, I can think of:
Option 1
Each client generates shared secret key (SK).
Now, is it safe to just directly send each client shared secret key over the network, which is then sealed and stored to disk for later use?
Option 2a
Should I derive a client shared secret from user password inside enclave and then send it over to the client?
Option 2b
Should I derive a client shared secret (SK) from user password one time(at registration probably) inside enclave and then encrypt it with server private key - a different key hard coded into enclave code: (SP-) - send it over to the client which is then decrypted with server public key (SP+)?
Option 3

Each of the client application has server public key (SP+) and the server application has each client’s public key (CP+).
Each of the client application generates the symmetric key (SK) and a challenge (n).
The client concatenates SK and ‘n’ (SK||n) encrypts with the SP+. The client application now signs the encrypted SK||n and challenge with the client private key (CP-). It is sent to the server application enclave.
On receiving the signed encrypted symmetric key, the server application enclave checks the authenticity using CP+ and then decrypts with its own private key (SP-).

Could someone just tell me which of these options are safe? If 2 or more option is safe, which one could be easiest to implement.


texts: Does Ciphertext policy ABE support search operation on encrypted data

texts:
Basically CP-ABE (or attribute based encryption) allows end-users to encrypt the data with desired access control structure. I was investigating the how to do keyword-search on encrypted data given the user has appropriate keys (may be like trap-door/delegation keys).

Interestingly the paper "Multi-user Attribute Based Searchable Encryption" tries to solve the same problem which is published in 2013 in IEEE. link  - (I think access to paper requires IEEE access, sorry for that)

Edit:

After some investigation found that:
"Enhancing Data Privacy in the Cloud", Yanbin Lu and Gene Tsudik, Iacr link proposes search leveraging on Predicate encryption as a function. - I am not sure if CP-ABE is related to predicate encryption and the search operation can be generaized for CP-ABE as well.

I am sure this problem might have been tackled much before also, so seeking some help from experts regarding Data search operation on encrypted data using CP-ABE scheme.

Thanks in advance.


texts: Small(er)-lane Keccak-f: impact and usage

texts:
Keccak defines a family of hash functions, by building a sponge out of a permutation Keccak-$f[b]: \{0,1\}^b \rightarrow \{0,1\}^b$. This permutation function is parametrised using $b$, which is the string length of the permuted block.

Keccak-$f[b]$'s block is further divided in $5\times 5$ "words" or "lanes" of length $w$, such that $b=25w$. The Keccak specification summary defines Keccak only for $w\in\{1,2,4,8,16,32,64\}$ or equivalently $b\in\{25,50,100,200,400,800,1600\}$. Typically, $b$ is chosen $1600$ (equivalently, $w=64$).

This makes me wonder: what applications have the authors in mind for small $b$ values? I can imagine a sponge construction for e.g. $b<400$ can become insecure, although these permutation functions are explicitly defined.

One example I could find was the Ketje Jr AEAD, which still uses $w=8$.


texts: Responsibility of quantum-weak cryptography

texts: At this point, should we consider it irresponsible to design new systems that assume hardness of problems already known vulnerable to quantum computers, such as factoring of large numbers or discrete logarithms? Likewise, do we have a moral obligation when answering questions about cryptosystems based on these, to ensure readers are aware of the coming insecurity?


texts: arithmetic calculation problem to quadratic arithmetic program


texts: Choices of $q$ and $f$ for RLWE-based constructions

texts:
I understand that RLWE was introduced to avoid the quadratic overhead in the matrices that appear in plain LWE.
However, I have a series of questions about this setting.
First, Ring-LWE-based constructions consider the polynomial ring $R_q = \mathbb{Z}_q[x]/(f(x))$, for some polynomial $f$ and some integer $q$. I've seen the choice $f(x) =x^{2^m} + 1$ and $q$ a prime such that $q\equiv 1\bmod 2^{m+1}$.

  Why is this choice of parameters relevant?

I understand that arithmetic in this ring is cheaper because of NTT, but, how does the CRT fit into the picture? Does it help the fact that the ring splits completely?

Also, I have a vague memory of some text that said that CRT is useful because instead of working with large modulus one can work with multiple smaller modulus.
I also heard that CRT is useful since you can do "parallel" computations.

  How does CRT fit into the RLWE picture?

Finally,

  Why does $q$ need to be prime?

Are there some works that consider a composite $q$?

Thanks! Any pointers or comments are more than welcome.


texts:
Wouldn't encrypting a message with AES, then encrypting the (randomly generated) AES key and IV with the EC public key suffice?

What attack vectors does ECIES protect against, that an AES-then-EC-encrypt wouldn't?


texts: Boolean circuit: can the output wire of a gate be used by many different gates in the next layer?

texts:
There are two typical secure multiparty computation paradigms using boolean circuits, namely garbled circuit and secret-sharing-based boolean computation. It is well-known that garbled circuits can be constructed layer by layer, in which each garbled gate has a fan-in of two and a fan-out of one (i.e., two input wires and one output wire). We have a similar construction in the secret-sharing-based boolean circuits. However, I failed to find any explicit comment whether an output wire of a gate can be used simultaneously by several gates in the next layer. In some available implementations of boolean circuits (e.g., this), no output wire is used more than once.
In my opinion, the reuse of an output wire does not undermine the security of the whole circuit since no information seems to be leaked by observing either the garbled gates or the secret-shared outputs. Am I wrong?


texts:
While reading Katz & Lindell's textbook (2nd edition) if found three main security definitions: ING-EAV-Security, ING-CPA-Security and ING-CCA-Security. (From this forum I know there are more, but these are the most basic ones). I also read, that ING-CPA-Security implies ING-EAV-Security and that ING-EAV-Security is weaker than ING-CPA-Security which is weaker than ING-CCA-Security.
My question: Does ING-CCA-Security also implie ING-CPA-Security?


texts:
a) if input 1011
= 0 1 1 1
b) if input 0110
=
1 1 0 0
my answer right?


texts: Undetectable cheater in Shamir's Secret Sharing scheme

texts:
Consider Shamir's Secret Sharing scheme with $n=5, t=3$ (i.e, there are 5 shares, and when we have 3 of them we can reconstruct our secret $s$). Let $f(x)$ be the dealing function, i.e the secret $s$ is defined as $s = f(0)$.

We assume that given 3 participants who gather together in order to reveal the secret, one of them wants to cheat in the manner of preventing the other 2 participants from revealing the secret. He doesn't care about the secret itself - he just want to sabotage the revealing of $s$.

I want to prove formally that neither of the 2 honest participants can detect who is the cheater.

My current lead is this: in the revealing process - using Lagrange's interpolation - each participant reveals his tuple $\left(x_i, f\left(x_i\right)\right)$ (where WLOG $\forall i : x_i \in \{1,2,3\}$), or perhaps just the unique function for that participant ($f_j(x) = y_j \cdot \prod_{1 \leq i \leq 3, i\neq j}\frac{x-x_i}{x_j - x_i}$ where eventually $\tilde{f}(x) = \sum_{j=1}^3 f_j(x)$ ) - but reconstructing this way only reveals a function $\tilde{f}(x)$ which they find out to be useless (when they try to use $\tilde{s}=\tilde{f}(0) \neq s$). It seems very intuitive that an honest participant cannot tell which $f_j(x)$ messed everything up, but I don't manage to write it formally. would appreciate some help... thanks.


texts: Consider the finite set Z_257 of non-negative integers less than 257. The number 257 is a prime, so Z_257 forms a field with addition and multiplication mod 257. How can I use the Extended Euclidean Algorithm to find the multiplicative inverse of the element 254 in this field.


texts: What is the collision resistance of a 2048-bit hash based on SHA-3?

texts:
Let $M$ denote the message. Let $B_i$ denote eight different bitstrings (chosen arbitrarily or randomly) such that $$0 \le \text{length}(B_i) \le 12345678.$$ Consider the following function (it outputs a 2048-bit hash of the input): $$H(M) = {H_1} \mathbin\Vert {H_2} \mathbin\Vert {H_3} \mathbin\Vert {H_4},$$ where $\mathbin\Vert$ denotes concatenation and $$\begin{array}{l}
{h_1} &= \text{SHA-3-512}({B_1} \mathbin\Vert M),\\
{h_2} &= \text{SHA-3-512}({B_2} \mathbin\Vert M),\\
{H_1} &= \text{SHA-3-512}({h_1} \mathbin\Vert {h_2}),\\
{h_3} &= \text{SHA-3-512}({B_3} \mathbin\Vert M),\\
{h_4} &= \text{SHA-3-512}({B_4} \mathbin\Vert M),\\
{H_2} &= \text{SHA-3-512}({h_3} \mathbin\Vert {h_4}),\\
{h_5} &= \text{SHA-3-512}({B_5} \mathbin\Vert M),\\
{h_6} &= \text{SHA-3-512}({B_6} \mathbin\Vert M),\\
{H_3} &= \text{SHA-3-512}({h_5} \mathbin\Vert {h_6}),\\
{h_7} &= \text{SHA-3-512}({B_7} \mathbin\Vert M),\\
{h_8} &= \text{SHA-3-512}({B_8} \mathbin\Vert M),\\
{H_4} &= \text{SHA-3-512}({h_7} \mathbin\Vert {h_8}).
\end{array}$$

Since all values of $h_i$ are the outputs of a simple MAC (which is known to be secure enough for SHA-3) and all values of $H_i$ are taken by extracting one cryptographically secure 512-bit hash of two independent 512-bit bitstrings, I would expect that the collision resistance of $H(M)$ is close to 1024 bits of security. Is this assumption correct?


texts: Getting the s-box input from its output in differential cryptanalysis on DES

texts:
If we try to get K4 using differential cryptanalysis on 4-variant DES, how can we get the input of a certain S-box if we know it's output?

This seems hard to do since the substitution operation is non-invertable for DES.


texts: Is PKCS#7 padding generated with a pseudo-random-number generator okay?

texts:
Let's take this PHP code. We use libsodium and libsodium-php.
You have $text, $senderPrivateKey, $recipientPublicKey and a $nonce. The latter was obviously created like this by just using Sodium:

$nonce = \Sodium\randombytes_buf($size);

Now this is the code which adds PKCS#7 padding:

/* determine random amount of PKCS7 padding */
$padBytes = mt_rand(1, 255);

/* append padding */
$textBytes .= str_repeat(chr($padBytes), $padBytes);

Afterwards this is encrypted using \Sodium\crypto_box_keypair_from_secretkey_and_publickey and \Sodium\crypto_box.

So is it okay to use mt_rand here? I mean in the PHP documentation it is discouraged to use this for any "cryptographic purposes". However here it is only used for choosing a ("random") character and the length of the padding.

So is this secure? Would using openssl_random_pseudo_bytes(), random_bytes (in PHP 7) or libsodiums \Sodium\randombytes_buf (like it is used for the nonce) be more secure?
And is this a correct implementation of PKCS#7? Especially as the same variable is used for the length and the character of the padding.

Edit: As there was some confusing here some more information: Actually this implementation is only supposed to hide the file size (especially for short pieces of data) a bit to prevent an attacker from guessing the plain-text message. This is implemented in some open-source libraries related to Threema and here is an issue about this.
So basically in the Threema client a cryptographically secure RNG is used where in this example here a unsecure PRNG is used.
And this is what this question is about: Is it less secure to use a PRNG here?


texts: How many messages before Sphincs(+) becomes insecure?

texts: How many messages would it take until the success probability of a forger becomes $1/2$? $1/4$?


texts: PKCS#11: Can C_GetMechanismInfo() return CKR_OK on a disabled mechanism?

texts: According to PKCS#11 v2.20, "C_GetMechanismInfo obtains information about a particular mechanism possibly supported by a token." Does that mean C_GetMechanismInfo() can return CKR_OK on a temporarily disabled mechanism? For example, if C_GetMechanismList() does not return CKM_MD5 in the result then is it OK for C_GetMechanismInfo(CKM_MD5) to return CKR_OK?


texts: Estimating random number entropy for input into 256 bit hash

texts:
Assuming a random number generation process outputs lots of numbers between 0-9. First I gathered up a bunch of the numbers, converted them to binary and created a bitmap.

Not so random as you can see! That must be why you shouldn't just use raw integers as random numbers in a computer program. Look what happens when the numbers are converted to binary:

0  00110000
1  00110001
2  00110010
3  00110011
4  00110100
5  00110101
6  00110110
7  00110111
8  00111000
9  00111001

As you can see the first 4 bits are always 0011 which is not very random. Even looking at the 5th bit that is not very random either. From 0-7 it is always a 0 bit and only for 8 and 9 is it a 1 bit.

What about the last 3 bits are they random?

0  000
1  001
2  010
3  011
4  100
5  101
6  110
7  111
8  000
9  001

It looks like there is all possible combinations of the 3 bits in the numbers 0-7 inclusive. However 8 and 9 bits are duplicates of 1 and 2. Does that matter? Should the numbers 8 and 9 be thrown away to remove bias?

I think the plan might be to run all these raw integers through a cryptographic hash such as SHA 256 then use that as a key. However what is the correct amount of raw integers to feed into the hash to get a quality 256 bit output? I assume I need 256 bits of input to get a good 256 bit output, yes?

If I do some back-of-the-envelope calculations I come up with:

3 bits of entropy per 8 bit (1 byte) number
256/3 = 85.33

This means I need to collect 85~ raw integers (682.67 bits) and feed them into the 256 bit hash. Does that sound about right?

Or would it be better to get the last 3 bits from each number until I have 256 bits of entropy, then convert that to hexadecimal and run that through the crypto hash? I think I've only seen a crypto hash algorithm take hexadecimal or text as input...


texts: How are RSA and ElGamal compatible in PGP?

texts:
I'm starting to play with PGP and I don't understand how if your key pair is RSA

you can encrypt a message for someone whose key is for example ElGamal.

How does the asymmetric key exchange work if the crypstosystems are different?


texts: Would increasing the "target space" of MD5 collisions make it significantly easier to find a collision?

texts:
This is tangential to this question, which asks about generating a file to match an exact MD5 hash.
My question is if it would be significantly easier to generate a file that is "within X digits of" an existing MD5 hash.
For example, if this is the MD5 hash I am trying to copy:
5f4dcc3b5aa765d61d8327deb882cf99
I would find these results acceptable as a 'copy' (differences are bolded):
5f4dcc3b5aa765d61d8327d5b882cf99
5f4dccab5aa765d61d8397deb882cf99
5f4dcc3b5aa765d61d8345debe82cf99
They are different, but without the bolded text would be difficult to detect with the human eye.
Does this significantly reduce the amount of time it would take to create an MD5 collision, given a hash, or is it on the same order? To say it another way, the fastest I was able to find was 2^24.1 (page 5), would having a larger "target space" significantly decrease this?


texts:
I'm trying to understand the MixColumns operation in AES but I have a question that I just can't figure out (it's probably something very simple but I can't find the answer).

The textbook explains that if you want to do a multiplication by 2 that can be implemented as a 1-bit left shift followed by an XOR.

How do I know what I XOR with?

Thanks!


texts:
In the RSA algorithm it's the the integer factorisation problem, it's easy to multiply the two large primes to generate n, but given just n it's very difficult to find the constitutent primes.

In the Diffie Hellman key exchange it's the discrete logarithm problem with the same principles.

Maybe it's just because it's maths I don't entirely understand but what is the one-way-ness of ECC, you 'dot' points together repeatedly to generate your key (in essence I'm sure it's more complicated than that (if I'm wrong please correct me)). But what is it that Alice and Bob both know that allows them to generate the key, quicker than Eve can?

I hope this question makes sense, thanks in advance.


texts:
We are given the following securitygame $G^{\text{LOSTNAME}}$:

Generate $k \leftarrow \{0,1\}^{\kappa}$ uniformly at random
Choose $h \leftarrow \{0,1\}$ uniformly random
Create decryption oracle $\mathcal{O}_{\text{Dec}}$ that on input c returns $Dec_{k}(c)$
Create a one-time test oracle $\mathcal{O}_{\text{Test}}$ that on $m_1$ $m_2$ returns $Enc_{k}(m_h)$
Call $\mathcal{A}$ with the security parameter and the oracles await $h'$
If $c*$ (output of the testoracle) was input to the decryption oracle ACCEPT/REJECT randomly
If $h'=h$ ACCEPT else REJECT

Now I should prove that IND-CCA -> LOSTNAME and LOSTNAME -> IND-CCA. The first direction is easy but the second one is not clear to me. In the IND-CCA setting we also have an encryption oracle, so an attacker on a scheme $\Pi$ would not be an attacker against LOSTNAME in my opinion. I also have no idea how I would prove that the encryption oracle can just be omitted. So how would I prove that the encryption oracle is actually irellevant? Any hint is highly appreciacted.


texts: I am a first year math PhD student with work experience and an MS in math.  Do you have any advice regarding internships involved with cryptography and other mathematics other than the NSA? Thanks.


texts: Using checksum instead of hash for authenticating ciphers

texts:
Lets assume for a specific situation we cannot use authenticated encryption like GCM ...

If we were to use CTR, what would you think of using a checksum on the plaintext then encrypt the whole.

The reason I don't want to use a hash is because the checksum is already presented in the plaintext protocol, and the reason I don't want to use standard authenticated ciphers is because of the extra hash size, even though it is just 16 bytes.

Thanks in advance.


texts: Does pairings based cryptography inherently require a CRS/trusted setup?

texts:
In all algorithms I've seen that rely on pairings-based cryptography (some examples: snarks without PCPs, more snarks, sublinear ring signatures), a common reference string is required. Is this always the case? If so, what is it about pairings (or the algorithms that use them?) that means the CRS is needed?

I know ZCash got around this by using MPC to emulate a TTP as described here, here, and here, but I'm more interested in understanding why the CRS is necessary. To clarify, I don't mean why the party that generates it needs to be trusted, as I understand that the public parameters of the CRS cannot be generated without use of the 'private' component that must later be destroyed, but I would like to know why the public parameters are required?

(I've looked at is pairing based crypto ready for productive use thinking it might answer this question but it doesn't)


texts: Why does bit padding work in practice in a message authentication code?

texts:
I understand that bit padding (add a 1, then 0's as needed) is a secure way to pad a message, preventing an unpadded message producing the same tag as a message that has been padded.

What I don't understand is how this works in practice. Surely a message exists that has a '1' bit followed by several trailing 0's. How does the system for a MAC distinguish between a regular message that naturally has a 1 and trailing 0's, and a padded message?


texts: Which groups to use for Pedersen Commitments

texts:
I have been reading about Pedersen Commitments, and have come across some  contradictory examples, which is confusing.

Just focusing on simple commitment of scalars (not EC points or vectors), then I have read this:

Why is the Pedersen commitment perfectly hiding?

which states:

  Public parameters - 2 primes , such that =2+1, and 2 elements 1,2∈ℤ∗ of order  (i.e 1,2 are generators of a q-ordered sub-group of ℤ∗).

  Secret parameter - ∈ℤ

  The scheme -  chooses ∈ℤ at random and sends the commitment =12(mod). Then  reveals ′,′ and  accepts iff =′1′2(mod).

and then I have read this version of the scheme:

https://tlu.tarilabs.com/cryptography/bulletproofs-protocols/MainReport.html#pedersen-commitments-and-elliptic-curve-pedersen-commitments

which states:

  Let q be a large prime and p be a large safe prime such that p=2q+1

  Let h be a random generator of cyclic group  such that h is an element of ℤ*q

  Let a be a random value and element of ℤ*q and calculate g such that g=ha

  Let r (the blinding factor) be a random value and element of ℤ*p

  The commitment to value x is then determined by calculating C(x,r)=hrgx
  , which is called the Pedersen Commitment.

  The generator h and resulting number g are known as the commitment bases and should be shared along with C(x,r), with whomever wishes to open the value.

My question is this:

p and q seem to be the same in each example.

In the first example, notice how the secret value is modulo q, the subgroup, whereas in the second example, the secret value, x,  is not modulo anything. Which is correct?

Also, in the first example, the blinding factor, r, is modulo the subgroup q, but in the second example, r is modulo the larger group p.  Again, which is correct?

I've also seen another variant where everything is modulo the larger group, not the subgroup.

Which variant is correct and does it matter?


texts: Converting common reference string to common random string

texts:
I listened to a talk on NIZK a while ago and vaguely remembered the speaker mentioned something like - A scheme that is statistically sound and computationally ZK in common reference string model could become computationally sound and statistically ZK in common random string model.
I couldn’t remember the exact talk and speaker, but I’m wondering whether this kind of duality is common in CRS constructions, and if so, how do we convert a scheme in common reference string model into one in common random string model?
Thanks!


texts: Is XTS-AES a NIST-approved nonce-misuse-resistant AES mode?

texts:
If I use XTS-AES and treat the tweak as a nonce/IV would the result be considered nonce-misuse-resistant?

I'm thinking of something like the following AEAD-like scheme:

enc(encKey, macKey, plaintext, aad):
  tweak = ... # 128 bits, generated like an IV or nonce

  # pad the plaintext to handle shorter-than-16-byte inputs
  # as well as determine the plaintext length after decryption
  a = AES-XTS(encKey, tweak, pad(plaintext))
  b = tweak || a
  return b || MAC([aad, b], macKey)

A tweak collision seems to only disclose whether the same plaintext was encrypted with the same key and the same tweak, which matches the definition of nonce-misuse-resistance I see here and differs from Rogaway's description of AES-SIV's properties in that the collision is apparent even if the AAD differs.

My motivation is looking for a nonce-misuse-resistant scheme that is NIST-approved. Having many existing implementations is also a benefit.


texts:
So I read some stuff about oblivious transfer and came a ross that 1 out of 2 OT can be used as a black box to build 1 out of n OT. At first it seemed trivial just feeding in 4 messages and 2 chooser bits but then I realized it's not that trivial since it doesn't guarantee security.
How is 1 out of 2 OT used to build 1 out of 4 OT if we can use 1 out of 2 OT as a black box?


texts: Showing that perfect secrecy implies adversarial indistinguishability

texts:
I've been reading the proof in these slides, the last page, and the author is using the lemma:
$Pr[A(c)=1|M=m_0]=Pr[A(c)=1|M=m_1]$
I understand on the intuitive level that it's a consequence of the assumed perfect secrecy, but can someone provide a proof to the aforementioned?


texts: Least-weak way to authenticate using only AES ECB/CBC

texts:
I have an embedded application that needs to occasionally get secure updates from a server. The only crypto library I have available for the chip is an AES-256 cipher (ECB and CBC, encrypt/decrypt).

Is there any worthwhile way to authenticate the message using only these functions and simple checksums? If I just did something like a 32 bit checksum of the plaintext and appended it before encryption, would that be vulnerable to attack (other than being only 32 bits of protection)?


texts: Regarding the secret sharing schemes, I am wondering if there are any academic references for the Additive Secret Sharing and its variations. Is there any textbook or article which has specifically discussed this scheme for secret sharing? When and where has it been formally introduced for the first time?


texts: Probability of finding a valid block when cryptocurrency mining

texts: Today I learned that for BTC, the probability of a hash being valid is approximately 1/(D*2^32), whereas D denotes to the difficulty. I was wondering if this is also the case for other cryptocurrencies or if this is something specific to BTC or the SHA-256 hash algorithm? If it is different for other cryptocurrencies, are there similar formulas for the probability of a hash being valid?


texts: How to verify a number encrypted with an unknown key

texts:
Alice and Bob are going to follow the protocol below.  Are there any crypto-constructions to help Bob verify the correctness of the answer he gets?:

Alice encrypts a set of numbers using some cryptosystem and a secret key (e.g. Paillier crypto-system).
Bob multiplies the ciphertexts to obtain an encryption of the sum of numbers.
Bob sends to Alice the ciphertext for the sum. Alice decrypts the sum with her secret key and then encrypts the sum with a key known by Bob.
Bob receives the sum encrypted with his key and decrypts it successfully.

Question: how can Bob verify that Alice didn't change the sum to a different number before re-encrypting?  Is some sort of zero-knowledge proof helpful?


texts: Why does TLS 1.3 support two CCM variants?

texts:
One of the important improvements introduced in TLS 1.3 is the pruning of the many previously available cipher suites to only five secure options (for symmetric ciphers), that are each supposed to have distinct advantages. For four of these, the advantages seem to be clear:

TLS_AES_128_GCM_SHA256: faster on systems with hardware support for AES/GMCM.
TLS_AES_256_GCM_SHA384: bigger numbers for regulatory (or marketing) reasons; resistant to Grover's algorithm.
TLS_CHACHA20_POLY1305_SHA256: faster in software with no AES acceleration.
TLS_AES_128_CCM_8_SHA256: useful for embedded devices that just want to reuse an AES circuit for both encryption and authentication; shorter tag.

However, I am still puzzled about the rationale behind the inclusion of TLS_AES_128_CCM_SHA256.

If I understand correctly, CCM with 64-bit authentication tags should be resistant against $2^{64}$ forgery attempts, which is also the maximal amount of messages TLS allows to be encrypted with the same key. So what is the added benefit of also supporting a version with 128-bit tags?

Of course I could be mistaken about CCM_8, and maybe it is not suitable for authenticating $2^{64}$ messages after all. But in that case, why doesn't RFC 8446 mention this in the "Limits on Key Usage" section? What am I missing here?


texts: why inverse in diffie-hellman protocol will not give same value?

texts: Security of diffie hellman protocol is $K=g^{ab}$.if sender want to calculate value of $b$(given $a$) he can do $g^{{{ab}^b}^{-1}}$(where K=$g^{ab}$) which will give $g^{a}$ as we are cancelling value of $b$ by finding its inverse. but it is not cancelling the value of $b$ and not give the output $g^a$. can any one explain why, while in ElGamal decryption in same way give plain text ($m=c2 *g^{ab}^-1$)


texts:
I have read a paper on Bit Slicing and Lightweight crypto but cannot understand how bitslicing makes encryption scheme faster.

Please can someone explain with an example exactly how bit slicing makes the code faster (even a single xor example will suffice)? Can bitslicing be applied to any encryption scheme?


texts: Why does a joint leakage MPC protocol not directly apply to a disjoint leakage requirement?

texts:
In the paper "Multiparty Computation Secure Against Continual Memory Leakage" on pg. 1239 the footnote at the bottom points out the difference between $joint$ leakage and $disjoint$ leakage.  The authors say the weakly leakage resilient protocol of BGG+11 cannot be directly used because it only applies to $joint$ leakage.

My understanding is the adversary has been made more powerful and is able to perform disjoint leakage (i.e. he can make leakage requests on random modules at any time).

I was wondering if somebody could explain this footnote a bit more clearly.  Why does a weakly resilient protocol not apply directly?


texts:
This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective.

RSA labs makes a similar statement:

  The discrete logarithm problem bears the same relation to these systems as factoring does to the RSA system: the security of these systems rests on the assumption that discrete logarithms are difficult to compute.

Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?

If you had a discrete log oracle could you use it to attack RSA?


texts: Exactly what RNG weaknesses endanger (EC)DSA?

texts:
RFC 6979 defines deterministic variants of (EC)DSA. It states in introduction

  One characteristic of DSA and ECDSA is that they need to produce, for each signature generation, a fresh random value (hereafter designated as $k$). For effective security, $k$ must be chosen randomly and uniformly from a set of modular integers, using a cryptographically secure process.  Even slight biases in that process may be turned into attacks on the signature schemes.

How can we characterize what RNG "slight biases" and more generally weaknesses allow attacks on (EC)DSA?


texts: Attacks on the RawCBC-MAC if the final step of encrypting with a second key isn't done

texts:
This is from Boneh's lecture ECBC-MAC

Here is also a link to the lecture itself - https://www.coursera.org/learn/crypto/lecture/QYT6i/cbc-mac-and-nmac
CBC-MAC with $(K_1, K_2)$ on a message $M$ applies RawCBCMAC with $K_1$ to message $M$ & takes the output tag & runs the PRF on the tag using a second key $K_2$
Boneh explains a chosen message attack on RawCBCMAC

Ask the oracle for the tag on a 1 block message $m$. Let's say the tag is $t$.
Now the same tag $t$ will also be the tag for a 2nd message $ (m || t \oplus m)$

Yes, this will indeed work.
I can think of another attack on the RawCBCMAC

Ask the oracle for the tag on a message $m$ (can be any number of blocks). Let's say the tag is $t$.

Ask the oracle for the tag on a single block message ($w \oplus t$). Let's say the tag is $t'$

Now the tag for the message $(m || w)$ is same as $t'$

Is this also a valid attack on RawCBC or am I missing something?


texts: Why is the Pedersen commitment computationally binding?

texts:
This is how the Pedersen commitment seems to work:

Let $p$ and $q$ be large primes such that $q \mid (p-1)$, let $g$ be a generator of the order-$q$ subgroup of $Z_p^{\star}$. Let $a$ be a random secret from $Z_q$, and $h=g^a \bmod p$.

The values $p$, $q$, $g$ and $h$ are public, while $a$ is secret.

To commit to a message $m \in Z_q$, the sender chooses a random $r \in Z_q$ and sends the commitment $c=g^mh^r \bmod p$ to the receiver; while in order to  open the commitment, the sender reveals $m$ and $r$, and the receiver verifies that $c=g^mh^r \bmod p$.

Moreover, the Pedersen commitment scheme is known to be:

information theoretically hiding: given a commitment $c$, every value $m$ is equally likely to be the value committed in $c$. For example, given $m$, $r$, and any $m^{\prime}$, there exists $r^{\prime}$ such that $g^m h^r = g^{m^{\prime}} h^{r^{\prime}}$. In fact, we have that $r^{\prime} = \frac{m-m^{\prime}}{a} + r$.
computationally binding: if the sender can find different $m$ and $m^{\prime}$ both of which open the commitment $c$, so $g^m h^r = g^{m^{\prime}} h^{r^{\prime}}$, then he can solve the discrete logarithm $\log_g(h)=\frac{m^{\prime}-m}{r-r^{\prime}}$. If we assume the discrete logarithm is hard, the sender cannot open the commitment with another value.

My question concerns the computationally binding property:

We know, from the information theoretically hiding bullet point, that given $m$, $r$, and any $m^{\prime}$, the sender is able to compute an $r^{\prime}$ such that $g^m h^r = g^{m^{\prime}} h^{r^{\prime}}$. But doesn't this mean that he's been able to open the commitment with a different message $m^{\prime}$ without even having to compute a discrete logarithm?


texts: Where can I find references to the theory behind PBC library?

texts: I don't know if this is the right place to ask this type of question. Anyway, I'm using PBC library for a project, but I'm a very newbie for what concerns pairing based cryptography. Then I ask some good references for Elliptic Curves Cryptography, possibly with some theory about groups or abstract algebra in general. I know this question has already been asked but I ask one thing more that I couldn't find: the theory behind the pairing_apply, in other words I'd like to know what is a pairing from a theoretical perspective. Where can I find some good explanation of this? On "traditional" books I couldn't find such a thing


texts: If Bob steals Alice's private key, how exactly would he read her encrypted documents?

texts:
So Bob grabs Alice's secret key when she isn't looking and her encrypted files, doesn't he need to know her passphrase to read her files?

What I am reading is that no he does not need it but as far as I understand GPG, it would still ask for a passphrase to decrypt a document.  Please explain why Bob would not need to know Alice's passphrase to read her documents in a step by step example.


texts: Software implementation of symmetric and asymmetric bilinear pairings

texts: I have recently read a paper about pairings, which only implemented asymmetric bilinear pairings and it mentiond that $\eta_{T}$ pairing is the most efficient algorithm for symmetric pairings. I wonder is there any software implementation on elliptic curves could achieve both asymmetric and symmetrci pairings e.g. $e(g,g), e(g,h), g\in G_{1}, h\in G_{2}$


texts: Question about variations on Vigenere cipher

texts:
I'm new here and by no means an expert on cryptography.  I like to dabble, and one of my favorite classical ciphers is the Vigenere.  I understand that the normal method of Vigenere encrypting is to add the corresponding number of the letter of the key to the number of the letter of the message, thus producing the cipher text for that particular letter.  My question is, regardless of key length, is it advantageous to alter the order in which the key is applied to the message?  For example, instead of moving forward through the alphabet to obtain the cipher text, what if I started off by going backwards?  Or if I alternated by going forward with the first key letter, then backwards with the second, and so on.  Or if I alternated by going backward with the first two key letters, then forward with the next two.  Would this make it any harder to decipher the message or make it more difficult to use letter frequency analysis to obtain the key?
I can provide examples if my question isn't clear.  Thank you in advance for any insight you are able to provide.


texts: How to calculate M when the attacker know e and w

texts:
Alice has a pair of RSA keys, the public key is $(n,e)$, the clear
text message $M$ and the ciphertext $C=M^e \pmod n$.

We suppose that Bob wants to encrypt two successive messages and send them to Alice, the messages are of the form, $M$, and $M+w$, the corresponding ciphers are $C$ and $C’$.

We suppose that an attacker intercepted $C$ and $C’$ and that he
knows $w$.

Find out how can the attacker calculate the message $M$, in the case of $e=2$.


texts:
I came across various definitions of what authenticity means in cryptography. I would like to know which one is correct.

The first definition - the one I always used - is the following:

  Data authenticity means that the initial message sender is who he/she claims to be.

According to this definition, we can have data authenticity without data integrity.

The second definition defines authenticity as authentication + integrity.


texts: Computational Complexity: ECC multiplication vs Modular multiplication

texts:
How does performing scalar multiplication on an elliptic curve compare to exponentiation in a multiplicative group modulo a prime?

I.e. on a given elliptic curve of size $|t|$, what's the complexity of computing $kP$ with respect to $|k|$ and $|t|$?

And in comparison, what's the computational complexity of a modular exponentiation of form $g^a \bmod p$ with respect to $|g|=|p|$ and $|a|$?

It would already be a big help to know the answer for double-and-add and square-and-multiply respectively.


texts: Clarification of RFC2246 with regards to Finished Message

texts:
I'm working on a client handshake finished message for a TLS client, and I'm reading through the RFC 2246 spec. The spec states (in section 7.4.9):

  The hash contained in finished messages sent by the server
  incorporate Sender.server; those sent by the client incorporate
  Sender.client. The value handshake_messages includes all handshake
  messages starting at client hello up to, but not including, this
  finished message. This may be different from handshake_messages in
  Section 7.4.8 because it would include the certificate verify message
  (if sent). Also, the handshake_messages for the finished message sent
  by the client will be different from that for the finished message
  sent by the server, because the one which is sent second will include
  the prior one.

Is anyone able to clear up what it means in the first sentence with regards to the Sender.server and Sender.client?


texts: Recovering the key in an ElGamal Signature Scheme variant

texts:
From page 318 in Stinson's "Cryptography: Theory and Practice", question 7.3:

Suppose that Alice is using ElGamal Signature Scheme. In order to save time in generating >the random numbers k that are used to sign messages, Alice chooses an initial random value >$k_0$, and then signs the $i$th message using the value $k_i = k_0 + 2i \mod (p-1)$ >(therefore $k_i = k_{i-1} + 2 \mod (p - 1)$ for all $i \geq 1$).
(a) Suppose that Bob observes two consecutive signed messages, say ($x_i$, sig($x_i, k_i$)) and ($x_i+1$, sig($x_i+1, k_i+1$)). Describe how Bob can easily compute Alice's secret key, $a$, given this information, without solving an instance of the Discrete Logarithm problem. (Note that the value of $i$ does not have to be known for the attack to succeed.)

In class we demonstrated how to solve for $k$ if $k$ was reused between messages, so I figured we could do something similar to that. However, this didn't work since a big part of that solution was to solve for $r \equiv \alpha^k \mod p$ since the $r$s were the same. This time, however, they aren't.
$$r_i \equiv \alpha^{k_i} \mod p $$
$$r_{i+1} \equiv \alpha^{k_i + 2 \mod (p-1)} \mod p$$
So we're kind of at a loss here on where to go. Basically all I've come up with so far is "solve for $k$ first since we can define any $k$ in terms of another". So if anybody could lend a hand, that'd be greatly appreciated.


texts: In the Paillier cryptosystem, is there a method to judge whether an encrypted number is less than 0 (without the private key)

texts: Or, is there a cryptosystem that is both order-perserving and additive homomorphic?


texts: is coin-tossing an instance of secure computation (MPC, 2PC, etc.)?

texts: Coin-tossing protocol is defined as a protocol between at least 2 non-trusting parties that allows them to obtain an unbias random bit in such a way that no involved party can influence the output. Hence, does it pertains to the notion of secure computation?


texts: Can using a cascade encryption decrease security?

texts: When using cascade encryption, can you actully decrease the security, for example if you do something wrong, or is it only depend on which algorithm or mode of encryption you use?


texts: Difference between symmetric and asymmetric hash function?

texts:
The Linux kernel supports symmetric and asymmetric hash functions. E.g. sha1, sha256, ...

See tcrypt.c and search for test_hash_speed and test_ahash_speed.

I know what the difference is between symmetric and asymmetric ciphers, where the encryption and decryption key is not the same.

Question

What is the difference between symmetric and asymmetric hash functions?


texts: On what basis is padding chosen in OpenSSL?

texts:
I am using CAPI Engine in OpenSSL and I did some test. When I use TLS 1.0 or 1.1, during handshake and RSA signing, PKCS padding is chosen. When I use TLS 1.2, RSA signing uses PSS padding.

What affects the choice among paddings?
How client knows what padding was used?
When is padding assigned to RSA structure?


texts: Bits of entropy needed to choose a random element from a list?

texts:
Suppose I want to choose a random element from a list of size $2^n$, for any integer $n$. (Here, random is to mean an equal probability of selecting every item.) My intuition says I'd need $n$ bits of entropy.  For example, for a list of size 64, I'd need 6 bits of entropy.
However, how many bits of entropy would I need to choose a random element from a list that's sized something other than $2^n$?  For example, for a list of size 3, or 10?
My intuition says that I'd need to find $n$ such that $2^n$ is a multiple of list size, to ensure equal probability of selecting every item.  (This is true for all lists sized $2^n$.)  However, that doesn't seem to work in practice: there does not appear to be any $n$ such that $2^n$ that divides evenly into 3 or 10.


texts: How can we sign a contract digitally between two parties?

texts:
I'm trying to sign a contract with another party, without using handwritten signatures.

I've just read through Applied Cryptography, but there doesn't seem to be a protocol that can solve this problem. Digital signatures simply don't work. Even if the other party signs the contract with his private key and I can verify it using his public key taken from a Certificate Authority, he can claim that he had lost his private key, and an imposer had signed the document.

In fact, he can shamelessly broadcast his own private key anonymously over the internet moments before he signed the document with me, thus securing his "proof" that everyone has his private key at a time before the document was signed. Besides this, there are many other reasons why digital signatures cannot achieve non-repudiation, as elaborated by D.W. in another post.

What alternatives do we have?

How can we make digital signing work?


texts: Linear cryptanalysis complete key guessing

texts:
In linear crypt analysis, partial sub keys are guessed and verified for its correctness with the help of plaintext and ciphertext.

From the partial sub key, how it is possible to guess the complete key?

For example, if we are guessing and verifying the key bits $K_5,K_6,\ldots,K_8,K_{13},\ldots,K_{16}$ for its correctness. But how can we get the complete key? That is $K_0, \ldots, K_{16}$.


texts:
I was recently trying to replicate a length extension attack on SHA1. I implemented the registers state and also the new padding implementation (with the whole of the message that I want to extend). And it works, I know the length of the key, so I'm able to get the total length of the message and forge a hash. However, when I try to brute force the length of the key (as it should be unknown), I always end up getting the same hashes for groups of 64 lengths, and not different ones for each. This makes sense for me, as I am padding the (original message + key) and so the length of the padded message should be the same for a certain number of key sizes, right? Does this imply that it is impossible to retrieve the key length? I think there is something wrong in my reasoning... Here is the code that I'm using:

for i in range(0, 200):

        specificLength = len(padSHA1(i * "a" + originalMsg) + "extension")

        forged = sha1ExtensionAttack("extension", registers, specificLength)

        print i, forged, payloadSHA, specificLength

        if forged == payloadSHA:
            print i, len(key)
            assert len(key) == i

            print "[*] Length of key is {}".format(i)
            break

When I run it with a key length of 49 I end up getting a success with a length of 43, which doesn't make much sense. Then, I get the same hash for lengths 43 to 107...

I'll be very grateful if anyone explains to me what's wrong with this approach, thank you!


texts: Hashing into a supersingular elliptic curve

texts:
Is there any way to hash from a string
$\in \{0,1\}^{*}$ into a supersingular elliptic curve $E(F_p)$ such that the hash function behaves(provably) like a random oracle, and is efficient?

Using Maurer's indifferentiability framework 1, one can prove that a cryptosystem using a random oracle is secure if the random oracle is replaced by an "indifferentiable" hash function. Brier et. al. 2 prove the conditions for a hash function to be indifferentiable from a random oracle, i.e. to put it simply, the hash function has to use an "admissable encoding" of elliptic curve points. They also provide a construction based on Icart's function that appears to work only on ordinary elliptic curves.

My question is, does there exist similar such constructions for supersingular elliptic curves? The Boneh-Franklin IBE requires the use of a hash function to a supersingular elliptic curve. They construct a hash function and prove that their IBE scheme is secure using the new construction. However, they do not prove that this construction is "indifferentiable" from a random oracle, or that this construction can be used in any other cryptographic scheme without altering its security.


texts: Mapping the hash of message to a point of elliptic curve for signature

texts:
Let the subgroup $G$ of elliptic curve constructed with point $P$ with prime order $q$ by $G=\langle P\rangle $. The $h(x)$ is a hash function. We want to map the hash of arbitrary message $m$ to a point in $G$ for use in the signature algorithm (such as BLS).
Why we don't use $k=h(m) \bmod q$ and then $S=kP$, whereas it is clear that the point $S$ is in $G$?
What is the flaw of this? security or efficiency?


texts: Diffie-Hellman problem: is DH still secure if $g^{a^2}$ is known?

texts:
Let, $g^{a}$, $g^{b}$ are known elements, where $g\in G$ and $a, b\in Z_q$. According to Computational Diffie-Hellman (CDH) assumption, it is hard to compute $g^{ab}$.

If $g^{a^2}$ is also known then is it still fall into Computational Diffie-Hellman assumption? In other words, if $g$, $g^{a}$, $g^{b}$, $g^{a^2}$ and $q$ are known, is it still hard to compute $g^{ab}$?


texts: Is use of pre-shared key for sharing session key in symmetric key cryptography vulnerable to MITM?

texts:
Consider the following protocol:

Alice                    ------------------------> R1     Bob
Alice        k(R1),R2    <-----------------------         Bob
Alice                     ------------------------> k(R2) Bob
Alice         k(S)       <------------------------        Bob

Where

k is pre-shared key, known only to Alice and Bob;
k(x) is the encryption of x under key k
R1 is a random number generated by Alice;
R2 is a random number generated by Bob;
S is the session key, generated by Bob.

Is this protocol susceptible to MITM? If yes, then how?


texts: Is it safe to send HMAC and plaintext in the same message?

texts: If a certain protocol sends $plaintext$ and its corresponding HMAC then is such a protocol prone to key extraction attacks ? Intuitively , HMAC is $ciphertext$ generated from $plaintext$, (although not an encryption of plaintext ), so the only secret being $key$. Will sending both of them together weaken the protocol ?


texts: Can FFT be useful in encryption of dicom images?

texts: I am doing a project on dicom images. I will be encrypting the DICOM image using AES-GCM algorithm. Before encrypting the DICOM image, i thought of taking FFT. Will it provide an advantage during encryption? if so can you explain?


texts: Proving that a scheme is $\epsilon$-perfectly secret

texts:
I am currently trying to solve the following problem (2.18) from the book "Introduction to Modern Cryptography (3rd edition)" by Katz and Lindell:
Let $\epsilon > 0$ be a constant. Say an encryption scheme is $\epsilon$-perfectly secret if for every adversary $A$ it holds that $Pr[PrivK^{eav}_{A,\Pi}] \leq 1/2 + \epsilon$.
Consider a variant of the one-time pad where $M = \{0, 1\}^l$ and the key is chosen uniformly from an arbitrary set $K \subseteq \{0, 1\}^l$ with $|K| = (1-\epsilon) \cdot 2^l$. Encryption and decryption are otherwise the same.
Prove that this scheme is $\epsilon$-perfectly secret.
I've tried the following:
$Pr[PrivK^{eav}_{A, \Pi} = 1]$ = $1/2 \cdot Pr[PrivK^{eav}_{A,\Pi} | b = 0]$ + $1/2 \cdot Pr[PrivK^{eav}_{A,\Pi} | b = 1]$
Assuming that the adversary is deterministic we can fix $m_0$ and $m_1$ generated by $A$. In addition, let $C_{m}$ be the set of possible ciphertexts derived from any given $m \in M$.
Then
$Pr[PrivK^{eav}_{A,\Pi} | b = 0]$ = $\sum_{c \in C_{m_0}} Pr[Priv^{eav}_{A, \Pi} = 1 | C = c] \cdot Pr[C = c]$
= $1/|K| \cdot \sum_{c \in C_{m_0}} Pr[Priv^{eav}_{A, \Pi} = 1 | C = c]$
For any $c \in C_{m_0}$, let $M(c)$ be the set of messages that can be encrypted to $c$. Therefore
$Pr[Priv^{eav}_{A, \Pi} = 1 | C = c] = 1 \cdot Pr[m_1 \notin M(c)] + 1/2 \cdot Pr[m_1 \in M(c)]$
Because if $m_1$ is not in $M(c)$, $A$ knows for sure that $m_0$ was encrypted. Otherwise, $A$ can only give a random guess.
Now, what is $Pr[m_1 \notin M(c)]$? In the best case, $A$ selects $m_0, m_1$ such that $|C_{m_0} \setminus C_{m_1}| = |C_{m_1} \setminus C_{m_0}| = 2^l - |K|$
As a consequence, $Pr[m_1 \notin M(c)] = Pr[c \in C_{m_0} \setminus C_{m_1}] \leq \frac{2^l - |K|}{|C_{m_0}|} = \frac{\epsilon}{1 - \epsilon}$
Thus, $Pr[Priv^{eav}_{A, \Pi} = 1 | C = c] = 1/2 + 1/2 \cdot Pr[m_1 \notin M(c)] \leq 1/2 + \frac{\epsilon}{2 \cdot (1 - \epsilon)}$
This implies that $Pr[PrivK^{eav}_{A,\Pi} | b = 0] \leq 1/2 + \frac{\epsilon}{2 \cdot (1 - \epsilon)}$.
Since the same holds for $Pr[PrivK^{eav}_{A,\Pi} | b = 1]$, $Pr[PrivK^{eav}_{A,\Pi}] \leq 1/2 + \frac{\epsilon}{2 \cdot (1 - \epsilon)}$
Can someone point me out where my mistake in this reasoning is?
Thanks in advance.


texts: Is it possible to validate an email address without the user actually revealing the email address?

texts:
Say hypothetically I want a service where users express their opinions. But those opinions are heavily dependent upon where they work, and the best way to prove that they actually work at a specific place is by having access to an email address there. However, the service must guarantee that it (or anyone other entity) cannot know the user's specific email address, or else the user won't express their honest opinions.

Is this do-able?

So say I work at companyx, and my email is bob@companyx.com. When I sign up for this service, the service needs me to prove that I have access to a valid, current email address at the companyx.com domain. However I do not want to type in anywhere that my email is "bob@companyx.com" because then the service would know that I own that specific address. The service does not care that I specifically own "bob@companyx.com", just that I own some valid address at "companyx.com".


texts: How do i approach file encryption using encrypt-then-mac?

texts:
I'm programming a cryptographic application that encrypts files, locked with the password the user supplies. It's not intended to be used in production. It's a project for me to learn more about encryption.

I have programmed the encryption part already, it's in C# and i'm using CBC as cipher mode.

I want to add authentication to my encryption and i plan on doing that by using CBC + HMAC(SHA256). I know that i have to HMAC the IV + Ciphertext. And yes i know BouncyCastle has an API that offers GCM(which is probably preferred over using CBC + HMAC), but the API's barely have any documentation and i read that CBC + HMAC is probably just as secure if done correctly. KeePass(Keepass) uses it too.

However i'm not sure how to go about generating keys for the HMAC and the encryption itself. If i understand correctly it's always best-practice to use different keys for different operations (and rightly so).
I'm currently encrypting the file content with a key that is generated by deriving a 256 bit key with the PKBDF2 algorithm(which takes a salt and does 10.000 iterations), but i need a key for the HMAC too. What is the best way to go about generating a key?

If you notice any mistakes and/or misconceptions in this post please tell me.


texts: Can you use the same key to provide a signature and a MAC?

texts: Apologies if this is a stupid question, but I'd be grateful if someone could provide an answer. I'm assuming that you need to use different keys to provide these functions, is that correct?


texts:
I want to manually create a GPG public key that can be imported into GPG, i.e. I want to create a file with a Public-Key Packet, a User ID Packet and a Signature Packet (for an example see here). I already managed to correctly create a Public-Key Packet with a User ID Packet and a Signature Packet, except for the hash/signature of the Signature Packet.
I tried to hash data as described in RFC 4880, however the description there is rather imprecise. For example it does not state what exactly constitutes a public key body (is it only n or also the public exponent e?) or if "tags" are to be hashed as well. With tags I mean fixed data preceding certain elements of a packet (e.g. for the public exponent e the tag is 00 11; see here).
Unfortunately the GPG source code and its resulting binary are also not very helpful for understanding what data exactly is hashed. I am currently tracing the export function (i.e. gpg --export) but I can't find the function that is used to hash the data for the Signature Packet (interestingly enough, neither the hash_public_key() function in g10/keyid.c nor the make_keysig_packet() function in g10/sign.c seem to be used for that).
Does anyone know what exactly is hashed and can exemplify it?


texts: Attack against factorization of $p-1$ of $\mathbb{Z}_p^*$ group

texts:
It is said that for the group $\mathbb{Z}_p^*$, the factorization of  $p-1$, is critical.

If $p-1$ has some small factors $q_1, q_2, q_3, q_4$, then when we transmit $g^x \bmod p$ where $g$ is a generator of this group, the attacker can derive $x \bmod q_1q_2q_3q_4$

How does it happen?

Can someone please provide a practical example, say for $p = 29$, where $p$ is prime but $p-1$ has a bunch of small factors?


texts:
Let say we have $N=pq$ (Both $p$ and $q$ are safe primes, meaning $\gcd(p-1,q-1)=2$)

let's assume $e$ is an odd number which can be efficiently factored and assume that we know the $e$'th root of 1 modulo $N$ - call it $r$ - as well es $e$ and its prime-factorization. There is a claim that knowing the $e$'th root of 1 modulo $N$ we can find such $y>1$ and an odd prime $p_0$ such that $y^{p_0} = 1 \bmod N$.

How can we calculate $y$ and $p_0$?


texts: Optimal bandwidth cost for Oblivious RAM

texts: Goldreich and Ostrovsky show that any ORAM algorithm must have bandwidth cost $\Omega(logN)$, where $N$ is the total number of blocks outsourced. This is in Theorem C of this paper. But they didn't give any proof for this Theorem. Is there other papers that have proved this theorem?


texts: Let $Y = xG$ be a point on an elliptic curve, $G$ the generator point and $x$ a scalar. Without knowing $x$, is it possible to calculate $x^nG$, being $n$ a natural number?


texts: Does selectively generating keypairs with particular public-key hash prefix weaken the security?

texts:
I'd like to embed 8-bits of information by selecting only keypairs where a hash of the public key begins with those 8-bits.  (The expected number of keypairs that will need to be generated is 256, so there is a little extra work required.)
The goal is to be able to determine the source of a keypair, to aid debugging in a distributed system.
Does selecting only keypairs, where a hash of the public key has a particular property, weaken security?  (Assume that the hashing function is irreversible.)
If so, how?


texts: Does the secret key used in AES have to prime?

texts:
I’ve looked around this site and the web quite a bit, but can’t find a definitive answer on whether or not the secret key $k$ used in the AES crypto-system has to be a prime number? Or can you just use any random values for the $128,192$ or $256$ bit long keys?

As a personal educational exercise, I’m working on my own implementation of AES, but my only other crypto experience is with the RSA crypto-system, though rather an elementary understanding, where the keys need to be prime, so I guess I just assumed the key for AES did as well. From what I gather the answer is “no”, but I don’t know enough about AES yet, to know whether or not that makes any difference?


texts: Knowing SHA256(m) and k, is it possible to calculate HMAC-SHA256(k,m)?

texts:
Cryptographic APIs use to allow for calculating HMAC-SHA256 signatures for message m and key k with something like HMAC-SHA256(k,m). However, I found out that none of them (unless I overlooked it) allows for calculating the MAC from the hash of the message, and key. IOW, the API to calculate HMAC knowing only h=H(m) and k is not available.

For example, Java provides the Mac class, but only allows for a buffer to be fetched so that the output (the HMAC-SHA256) is calculated.

Does this cryptographically makes sense, and if yes, any clue on how to implement this in Java?


texts: Enumerating the bias of NIST and Pearson randomness extractors

texts:
The following is an extract from a paper about using your mobile phone as a true random number generator (TRNG). The mobile phone bit is incidental to this question though.  I'm interested in the calculated bias of the $M \times r$ matrix extraction mechanism. Specifically equation 5 at the bottom.

A. Does a similar bias equation exist for a cryptographic hash based extractor such as SHA-X? NIST advice simply states that if you extract less than half of the input entropy, you'll be fine.  If you plug in values for SHA-1 with a 320 bits of entropy input you get   $\epsilon = 2^{-80}$. That's below the NIST (DRAFT Special Publication 800-90B, August 2012) bias threshold of $2^{-64}$ for declaring a sequence as having 'full entropy'. I suspect that it is exactly the same equation, and that it's generic to all extractors.

B.  Could one derive another similar bias equation for using an 8 bit Pearson hash as an extractor? Using Pearson with it's random permutation is not a million miles away from a vector matrix. Yes it's got that XORy thing in it, but otherwise the transmission of bias principle must still exist, and equally similarly must depend on the length of the input entropy.

Part A takes precedence.


texts:
Are there any algorithms that exist to encode messages written with pen and paper such that the messages can be encrypted/decrypted mentally? For example, Bob thinks of the text "This is my plaintext", writes down "siht si ym txetnialp", and then Larry (who knows the cipher) is able to understand the message "This is my plaintext",  just by looking at the cryptotext. The algorithm is simple enough that nothing needs to be written down besides the cryptotext.

This should not be a code, where a specific phrase means something else. I'm looking for an algorithm like a one-time-pad or modular addition method that can be completely contained in one's head.

The strength of the encryption is not as important - it doesn't need to stand up to a complex solver, just be very difficult to decode by someone who doesn't know the cipher. The more important feature here is speed - e.g. encrypting and writing a message can be done simultaneously in (on the order of) twice the time it takes to write it in plain English.


texts: Block cipher does not provide security by itself

texts: What is this statement all about? When I look at a block cipher it seems pretty hard to break it and the mathematics behind insure a good complexity. It may refer to key generation, initialization vector (IV), padding scheme ?


texts:
For a protocol, I need to blind a ciphertext. I am not sure how to choose the blinding factor. How should I choose the range? What should I consider to offer security?

I am using CKKS scheme, the one in SEAL.


texts: With randomized encryption, ciphertexts must be slightly longer than plaintexts in order to allow for more than one possible ciphertext per plaintext

texts:
Can anyone give me a simple example of this?

  "For example, if there are $2^{64}$ possible cipher texts per plain text,
  cipher texts must be at least 64 bits longer than plain texts"

This is what book said but I don't really get this.


texts: Seeking an implementation of the Satoh algorithm for elliptical curve point counting

texts: I would be very grateful if someone has an implementation of the Satoh algorithm (Fast Elliptic Curve Point Counting). Can someone point me to practical algorithm implementations or provide some examples? Everything I can find is just an article.


texts: What the X stands for in the front of Elliptic curve names like X25519

texts:
I have seen Curve25519 and X25519, Curve448 and X448. I've seen a small note in this answer

(Historical note: Originally, X25519 was called Curve25519, but now Curve25519 just means the elliptic curve and X25519 means the cryptosystem.)

Is it a standard to say CurveABC is the Elliptic Curve and XABC is the cryptosystem?
Or, it is just a convention between the Elliptic Curve Cryptographers.


texts: How much work is required to find multiple collisions for a hash function?

texts:
Assume an ideal hash function of output size n bits, finding one collision requires approximately 2^(n/2) evaluations of the hash function using a birthday attack.

However, how many evaluations are required to produce two or more collisions?

Note I am talking about distinct collisions i.e. $H(A)=H(B)$, $H(C)=H(D)$, etc.


texts: How is a PRP different from PRF? Both can be inverted to get the same input

texts:
PRP is said to be a bijective function which means that there is a one-to-one mapping with the output. And hence the output can be inverted using the decryption algorithm to get the same input.

Question is how's PRF different from that. If it is not bijective, how are we going to decrypt the message?

In counter mode it is said that we are using a PRF and not PRP (unlike CBC) i.e. we are not using the decryption capabilities of block cipher. What does this mean? We are anyway going to decrypt the message by XORing the IV counter and the key with the cipher text. Then why is it said that we are not using the decryption capabilities? and how is it different from PRP that has to have a decryption algorithm?


texts:
I have two keys and they have the same KCV. How is this possible?

I have encrypted data with both keys and I have the same result. Both keys are the result of the derivation of the same IMK, one was done by a software and the other one was done by manual process.

Key A: 04 A4 49 F2 DC 46 D3 2A 3E A7 C7 E3 D3 A1 AB BA
Key B: 05 A4 49 F2 DC 46 D2 2A 3E A6 C6 E3 D2 A1 AB BB

Data: FF FF FF FF FF FF FF FF 11 11 11 11 11 11 11 11

Encrypted with key A: 22 17 FE 9C BC 6E DC F1 F2 D1 13 CA 70 74 54 AA
Encrypted with key B: 22 17 FE 9C BC 6E DC F1 F2 D1 13 CA 70 74 54 AA


texts: Determine safety of exercise hash functions

texts:
There have been several attacks against hash functions such as $h_{sha1}$ and $h_{md5}$.

Professor A suggests a new function $h_{666}$ with an output length of 666 bits.

Professor B suggests combining the two functions $h_B=h_{sha1}(h_{md5}(m))$.

Professor C suggests combining all four functions $h_C=h_{md5}(m) \oplus h_{sha1}(m) \oplus h_B(m) \oplus h_{666}(m)$, where short messages are padded with zeros where necessary.

  Explain / prove why each and every one of these functions may be less safe than $h_{sha1}$.

I couldn't think of anything to say about $h_{666}$, since we know nothing about it, except that it has a constant output length, which I know many other hash function have. I thought it might have to do with the length not being a multiplication of 2, but couldn't reach a specific conclusion.

I think $h_B$ is bad because we know that $h_{md5}$ is known to have collisions, and such collisions will affect $h_B$ as well.

Couldn't exactly understand what's wrong with $h_C$, unless again it has to do with collisions of $h_{md5}$ and/or the safety of $h_{666}$.

Any help would be appreciated, thanks!


texts: how researchers extract encryption times when randomness is involved?

texts: I have seen some research papers where they compare encryption/signature times on elliptic curves.But when i have implemented the algorithms and calculated encryption times but each time i get some different timing.i thought this was due to random scalar chosen for scalar multiplication in el-gamal encryption scheme.So do researchers take average or min or max of the values they obtain?How do they get those execution times when randomness is involved?


texts: Cascaded XTS vs XTS with cascaded block ciphers

texts:
The popular VeraCrypt encryption utility, as well as its precursor TrueCrypt, has the option to cascade multiple ciphers on top of each other, such as AES-Twofish-Serpent. It works by cascading three ciphers running in XTS mode. Potentially unnecessary security benefits aside, I am curious how this differs functionally from using a single instance of XTS with a block cipher defined as three cascaded ciphers. Each block cipher uses a different key, expanded from a 512-bit master key with a hash-based KDF.

The only thing I can think of is that the total keyspace would be less, as each XTS increases keyspace. What differences are there between the two schemes in terms of theoretical security or performance?


texts: Analysing communication complexity of a protocol

texts:
My question is more about the practical side of designing crypto. protocols and it is related to complexity. So, if you think it's irrelevant to this forum please kindly let me know and I will remove the question.

In many crypto. protocols the communication cost is very important. In the following, I consider a client-server protocol where the server computes a single value and sends it to the client. Assume the protocol requires modular arithmetics at a server-side on a finite field of size 120 bits, i.e. $\mathbb{F}_p$, where $|p|=120-bit$. Assume we have improved the previous protocol and now we can work on a smaller filed, e.g. $|p|=80-bit$.

As we know we cannot say the communication cost has been reduced by $40$ bits, as the value can be $1$ or  $119$ bits value, because it involves a modular operation.

Question: How do we analyze/argue the communication improvement of the above protocol?


texts: Advantages of HS1-SIV over ChaCha20-Poly1305-SIV?

texts:
What advantages does HS1-SIV have over ChaCha20-Poly1305-SIV?

I know that both use the ChaCha stream cipher, but I am trying to understand why HS1-Hash is a better MAC.

Edit: To hide the Poly1305 result I would use of the ChaCha20 core, a.k.a. HChaCha20, as a nonce-free but keyed PRF.  This works because ChaCha20 is really a keyed hash in counter mode, and can also be used as a PRF directly.  In fact, this is what XSalsa20 does with Salsa20 – it uses the Salsa20 core as a PRF to generate a 256 bit subkey from a 256 bit key and 128 bit nonce, the other 64 bits being used as the nonce for the subkey.  Since HChaCha20 is a strong PRF (ChaCha20 is broken otherwise), I can just use it as a keyed 128->128 bit PRF, by discarding the top 128 bits.


texts: Why does the DES crypto algorithm NOT use 2 rounds?

texts: Now, if we were to go round by round, you could give a distinct reason for not using a single round since after just one round, the right half of the text comes directly, as-is, to form the left half of the new text after the one round. In this way, if an observer were to notice this, he/she could deduce that DES may be the algorithm being implemented. But is there a way of figuring out that DES is being used after performing TWO rounds?


texts: Optimized Garbled Circuit Algorithmic Description

texts:
The Garbled Circuit (GC) is now over thirty years old, and many optimization methodologies have been proposed, including point-and-permute, row-reduction, free-XOR, fixed-key blockcipher, half-and.

But, after Googling papers and forums, I can't find any concrete algorithmic descriptions which includes all of these optimizations. Does anyone know the exact descriptions of optimized GCs?

I ask because I need to implement the algorithm for personal use.


texts: Fully Homomorphic Encryption over the Integers - perform an operation on an encrypted data

texts:
In Fully Homomorphic Encryption scheme represented here Fully Homomorphic Encryption over the Integers
In the Evaluate process (see section “3.1 The Construction” of the paper):
$$Evaluate(pk, C, c1, \dots , ct):$$
Now…

If I want to do some operations on an encrypted data, should I convert that operation to a binary circuit, then do the operation, and re-encrypt the final result?

If I have this simple binary circuit below, how could I evaluate the process?

What is the data that will be passed to the Input A and input B?

And how can I determine the number of addition and multiplication operations that will be used?

I did not understand how to do it from the Paper.


texts: Is there a program i can use to find a hidden message in a BMP file?

texts: I am working on a puzzle and think there is a message hidden in one of the files that is a BMP file. I am wondering if there is a program somewhere that could find it?


texts: Simplified Fiat-Shamir example generates wrong output

texts:
I am trying to implement the Fiat-Shamir identification protocol, however the end results always fail to match. I am using algorithm's description from here.

Preparation:

Select 2 prime integers and their product:

n = 19 * 23 = 437

Select s coprime to n:

s = 242

Compute v:

v = (s^2) % n = 6

Now the round:

Select random r between 1 and n - 1:

r = 410

Calculate x:

x = (r^2) % n = 292

Choose e either 0 or 1:

e = 1

Calculate y:

y = (r * s^e) % n = 21

Now if y^2 equals (x * v^e) % n then it's accepted. However in my case

y^2 = 441
(x * v^e) % n = 4

Why don't these numbers match? What am I doing wrong here?


texts: How to optimise Euclidean Algorithm for large numbers? -RSA

texts:
I am using the standard version of the Euclidian Algorithm (i.e. GCD(270, 192) = GCD(192, [270 % 192]) =  ...repeat until 0) to determine if two numbers are coprime. I run the algorithm, check if the GCD is 1 and use that to determine if they are.

The problem is that I'm doing this for RSA and when I test the algorithm with 5 or 6 digit numbers it takes about 4 seconds, so I need a way to optimise the algorithm to work with hundreds of digits. I found references to the Extended Euclidean Algorithm online, but to my understanding that is used for checking the modular inverses that you create.

Can anyone confirm that the Extended Euclidean Algorithm should be used for this purpose, or suggest another algorithm that can be used to calculate the GCD of 300 - 600 digit numbers?


texts:
If Enc is a PKE(Public Key Encryption) with key generation algorithm KG and message space $M = \{0, 1\}^n$, and SE is a Symmetric Key Encryption(SKE) with key space $\{0, 1\}^n$ and message space $M' = \{0, 1\}^*$ then the hybrid encryption
uses the same key generation KG, but its message space is $M' = \{0, 1\}^*$ and its encryption procedure $Enc'(p_k, m)$ picks a random symmetric key $k \gets \{0, 1\}^n$ and outputs ciphertext $(c, c')$ where $c = Enc(p_k, k)$ and $c' = SE(k, m)$. The decryption given $(c, c')$ decrypts $k$ from $c$ using the private key corresponding to pk and then decrypts $m$ from $c'$ using $k$.

If Enc is a CPA secure PKE on $M = \{0, 1\}^n$ and SE is IND secure SKE on$ M' = \{0, 1\}^*$,  is Enc' CPA secure PKE on $M'$?

If Enc is CPA secure PKE and SE is CCA secure SKE, is Enc'
 CCA secure?


texts: Why is CBC based on AES malleable in blocks other than the first block?

texts:
Perhaps I don't understand the answers to Malleability attacks against encryption without authentication, so trying to be more concrete... please be patient.

If I want to change the first block and I can change the IV, I see that its easy to change the IV to IV xor old_block_0 xor new_block_0 and the first block would change.

However, if I want to change the second block block_1, I don't understand how can I do it? If I change the block before it to block_0 xor x I would garble the D(block_0), won't I?