While there are ways to encrypt and decrypt information, most of these seem quite computation-heavy. Because of this I am thinking about splitting decryption into two parts - one is computation heavy and the other one is computation light. First part is performed on the remote untrusted server using some kind of session key, while the second part is done on the client side knowing the actual key.

User has a key K and there's encrypted information T on the server. User generates some K1 from his K and sends it to server. Server attempts to decrypt T with K1 and gets some T1 instead. It is not yet completely decrypted and neither of T, T1, K1 allow server to compute K. However K1 is generated in a way where user can easily decrypt T1.

Is this approach possible at all? What could be potential problems?

Update: I've come up with an example of how it could be done: User generates multiple keys - K1, K2, K3 ... KN, shuffles them and adds his own key K in the mix. Then he sends all those keys to the server and asks it to decrypt T with each of these keys. Server doesn't know which key is the correct one, while user knows which of T1 .. TN is the actual decrypted information while the rest is garbage. This particular approach has a lot of inherent weaknesses, as well as it doesn't allow to use the server for encryption (i.e. it's "read-only"), but it's kind of what I'm looking for.

Update 2: (Since I've spent my reputation on bounty I can't comment on answers anymore). The idea is to have a function that can be applied to a key and it's reverse function that could be applied to a "plaintext" that are easy to calculate and that can not be predicted by server (i.e. not constant for sure). The "generate garbage" and "discard garbage" are examples of this. The "generate hash from key" and "do nothing" are not good enough - server can simply omit the encryption, so this would only work if the hash is different for each session.

I do not know if this is possible at all, but I can't also prove it impossible.

  • 3
    Please give a real world example of your 'servers' because for todays equipment quite computation-heavy is not an issue. This sounds like a hypothetical issue. – user13695 Jun 7 '16 at 12:01
  • I am thinking about web-based client. While there is pgp implementation in JS i don't think it is the only possible approach. – aragaer Jun 7 '16 at 12:07
  • 1
    You can possibly double encrypt using a lightweight and heavy stream cipher. JavaScript is slow with regards to decryption, but it shouldn't be much of a problem to decrypt small pieces of information (see e.g. SJCL). Note crypto using JavaScript (in the browser) is kind of a security nightmare, there are quite a few articles on that. Use TLS! – Maarten Bodewes Jun 13 '16 at 11:54
  • 1
    The problem with the model is that if the server is untrusted, that is, you can not trust him at all, your security is only as strong as your lightweight encryption on client side. You do not add any protection if the attacker controls the server. Please define better the securty model, what attacks are you trying to avoid? Is the server really untrusted? Or just partially trusted? What can an attacker do on the server? – CristianTM Jun 13 '16 at 14:46
  • 1
    Passing multiple to keys to the server and hoping it "doesn't notice" which one yields the proper data is naïve and misguided at best. In almost all cases, the decrypted data is going to be (or contain) easily recognized file types. The next biggest problem is you're going to be needing to use N times more processing power and bandwidth. If you don't trust the server, it shouldn't handle decrypted data AT ALL (potential lighter weight schemes aside). – Clockwork-Muse Jun 17 '16 at 13:42

Your premise is incorrect, but conceptually I think the problem you're alluding to has been solved by server based password managers using password based key derivation functions (e.g. PBKDF2).

Reason your premise isn't right is that symmetric encryption and decryption (e.g. AES) is fast even in JavaScript. These days the cost is low especially when many consumer devices have dedicated hardware to process it.

Asymmetric encryption (based on public and private keys) on the other hand is expensive, and if its processing becomes prohibitive in an application there's a good chance it's being mis-applied.

Although with an algorithm like AES encryption and decryption is fast, if you don't know the correct key it will take forever to guess the right one because there are way too many to guess (especially with 256 bits). This is further compounded by the use of PBKDF2, which I shall explain in a bit.

Although you say the server is untrusted, you do trust it enough to receive and store your encrypted data, but I assume you don't trust it to directly receive and store any sort of confidential data in plain text. Another assumption I will make is that the server will try to ensure the encrypted data is only sent to you, and not to everyone who simply asks for it. Assuming this is reasonable I will present a scheme using PBKDF2 that many server based password manager services utilize.

What's PBKDF2? It creates a key from another key, much like your K to K1. What's interesting about PBKDF2 is that it can be made as fast or as slow as you want - the larger the number of iteration rounds the slower it is.

Registration with server in order to establish authentication credentials and submit encrypted data:

//// JavaScript client side
PBKDF2(password, 1000 rounds) => encryption key // fast because low number of rounds
encrypt(encryption key, data) => encrypted data // fast even with AES 256
hash(encryption key) => auth key

// send encrypted data and auth key to server

//// Server side
PBKDF2(auth key, 100000) => server hash // slow because high number of rounds
// store server hash and encrypted data

When you subsequently access server:

//// JavaScript client side
PBKDF2(password, 1000 rounds) => encryption key // fast because low number of rounds
hash(encryption key) => auth key

// send auth key to server

//// Server side
// verify auth key
PBKDF2(auth key, 100000) => server hash // slow because high number of rounds

// if server hash matches what was previously stored return encrypted data
// send encrypted data back to client

//// JavaScript client side
decrypt(encryption key, encrypted data) => data // fast

Note that my reference to PBKDF2 above is a simplification to demonstrate its role rather than actual usage.

I believe this proposal solves the inherent problem that I think you're asking, without needing a new type of encryption, and instead rely on known strong cryptographic techniques. Everything on the client JavaScript side is pretty fast since you know the password/key, whereas trying to get your encrypted data then breaking the encryption from the server side are expensive.

Highlights of the proposal:

  • Everything on the client side is quick.
    • PBKDF2 has low number of rounds so is fast
    • AES encryption and decryption is fast
  • Server never privy to:
    • Plaintext password.
    • Confidential (decrypted) data.
  • Server stores encrypted data. To get any information from here is expensive.
    • Authentication required to obtain the encrypted data is relatively slow. First line of defence.
    • If a malicious entity somehow manages to get the encrypted data, they will still take pretty much forever to decrypt since they do not know the encryption key. Second line of defence.
| improve this answer | |
  • Just to confirm - the "auth key" is different for each session, right? Because otherwise user can't even trust server to perform that actual encryption/decryption. – aragaer Jun 18 '16 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.