MEGA: Malleable Encryption Goes Awry
mega-awry.io
mega-awry.io
I think this attack is really interesting and novel, but 512 login attempts is pretty high. I have a Mega account and I think I've logged in less than 50 times in the entire lifetime of my account, including when it was still controlled by Kim Dotcom. If you're an interesting enough target to use this on, I don't see why the Mega server that delivers the javascript for encryption can't be compromised instead, and just harvest the passphrase when it's submitted to login the first time?
I don't know what you'd have to do to convince someone to login 512 times via social engineering, either. Presumably, a user who is dedicated and uses the service on a daily basis might hit this through normal usage in a year and a half? That's definitely plausible, but how many users are initiating new logins each time? How many will just stay logged into the app and never login?
I guess for some percentage of people (e.g., people who are logging in each time via Tails, and do it twice a day) this attack is acutely viable, but it surely can't be all users.
To conceal them might be possible in some cases, but requires tampering suspiciously with public source client-side apps
This isn't a cryptosystem, it's a CTF level.
You don't have to take my word for it; that's how Mega summarizes the attack in their response.
From the link I just posted, written by the researchers:
'Nevertheless, on the clients that we analyzed, all attacks would have required a substantial number of manual login attempts (i.e., the user entering the password). Since clients usually cache the credentials, users often stay logged in, minimizing the number of logins performed and thereby increasing the difficulty of the attacks.'
> I have a Mega account and I think I've logged
> in less than 50 times in the entire lifetime of my account...
You know a million times more about cryptography than me, but it doesn't change the fact that I, personally, am not compromised by an attack that requires me to log in that many times.
Even if its a lot given average user behaviour, that's an incredibly low margin for safety
You've picked a sort of strange hill to die on when you find yourself arguing that a system is in practical terms secure because it's unlikely you're going to log in enough times to trip the bug that coughs up your private keys. If you have to compute the number of times you can safely log in, something has gone terribly, terribly wrong.
Same experience here. I've logged in maybe once per year, if it suddenly started asking me to login every time I used it, it would be a huge red flag.
It always surprises me how fragmented the entire space is: Syncthing "untrusted devices" support is still experimental, Nextcloud does support encryption, but it's hard to judge how trustworthy it is. Gocryptfs and ecryptfs should be solid, but they are hard to use in a browser or on mobile. Resilio, Borg, Tarsnap, EteSync -- yet more protocols, and without clear security analyses.
Same holds for commercial cloud operators: support for client-side encryption is starting to appear (Google Drive), but without an open, standardized client you still need to trust software from the cloud provider, which mostly defies the point of encrypting in the first place.
I worry this then just means government actors only will need to find 1 vulnerability to have open access to a standardized web and those vulnerabilities will exist, nothing is perfect. I genuinely believe a non-standardized approach is more effective even if they are each more vulnerable individually.
Android presents a decent corollary here vs iOS. Finding an iOS device exploit may cost more money but you get access to such a massive amount of devices it is worth it.
In addition a lot of security when things are fragmented tends to become "security through obscurity". Something that is a small player in a market can still have all sorts of issues that a state-funded actor can find via analysis and exploit. It's also much less likely to have a public actor find and disclose the issue due to the small install base.
For instance, the weird authentication scheme that gives rise to the RSA key recovery attack --- that problem is what PAKEs are for.
That is my point exactly, it should be how they think about it. Attacks to the cryptography math itself are only a single vector, the software implementation of it is going to have holes not to mention those beyond it from the hardware at the chip level to the firmware that runs it there are vulnerabilities well outside the math itself.
They make it look like its designed as a core part of the product on the website, while in reality its an after thought and its behind on updates too.
As good as Nextcloud sometimes is, a parts of it feel very legacy and unmaintained.
I did analyse the security of Tarsnap as I was writing it, for what it's worth.
Why does TLS make you twitch? Does that apply to TLS 1.3?
[1]: https://loup-vaillant.fr/articles/rolling-your-own-crypto
But frankly I trust my ability -- both now and in 2007 -- to use standard cryptographic algorithms to build a new protocol far more than I trust my ability to remove all the crap from TLS 1.1.
(Did you deliberately not mention heartbleed?)
The threshold question is, "could this vulnerability be reasonably expected to recur in independent implementations of the protocol?"
As for stripping back TLS 1.1 --- it wouldn't take much more than simply picking a single ciphersuite and requiring TLS 1.1. You wouldn't need to know, for instance, about export ciphers.
I get why you didn't use OpenSSL. The normal thing for someone like you to do in 2022 would be to use Noise.
Quick search shows WireGuard protocol, but I am not sure if how much of the WireGuard protocol is the same as the Noise Protocol.
https://www.wireguard.com/formal-verification/ https://www.wireguard.com/papers/wireguard-formal-verificati...
The WireGuard protocol is extensively detailed in [2], which itself is based on the NoiseIK [3] handshake.https://duo.com/labs/tech-notes/noise-protocol-framework-int...
Noise is used today in several high-profile projects:
WhatsApp uses the "Noise Pipes" construction from the specification to perform encryption of client-server communications
WireGuard, a modern VPN, uses the Noise IK pattern to establish encrypted channels between clients
Slack's Nebula project, an overlay networking tool, uses Noise
The Lightning Network uses Noise
I2P uses NoiseFor whatever it's worth, we had an external analysis of the protocol done recently at EteSync. Though even before it, we (intentionally) only used known and common primitives (from libsodium) to ensure that we have a solid base from both the cryptographic schemes, and the actual implementations.
This is a great teaching example for the “don’t roll your own crypto” proponents.
(I should add: disclosure, I work there too.)
The crypto design is brittle, but the practical attacks are somewhat limited. The reason why it's so disparaged by cryptographers it because it ignores several decades of cryptographic advances -- the whole saga of attacks on SSL / TLS<=1.2 taught us that key separation and clear protocol composition boundaries are important, but Telegram fails disastrously at these. Security proofs should be made before a protocol is used, not as an afterthought.
The real reason why I would not recommend Telegram is that chats (by default) and group chats (by necessity) are not encrypted. Telegram's servers will be eventually breached by someone. A malicious actor will be hired as a software engineer, or as an intern. When this happens, all you ever wrote in Telegram will be a plaintext at their disposal -- unacceptable in 2022, and post-Snowden.
The interesting part is really just the first step - starting with a user's password, to statically derive a service-authentication key and a data-encryption key that the service provider ostensibly never sees.
At $DAYJOB we independently came up with this same zero-knowledge solution too, using slightly different primitives. Ideally there'd be some well-reviewed zero-footgun nacl.SecretBox()-style thing for this use case, but there simply isn't.
Most people face a choice between rolling their own crypto or not using it at all.
Can you provide a link? That one's hard to Google.
There is a whole hellacious amount of mechanism in this protocol that doesn't seem necessary at all. I don't know if doing it simply would involve more keys or less keys but it would certainly seem to involve fewer concepts and less ad-hoc invention --- PAKEs are a solved problem, KDFs are a solved problem, key-wrap encryption is a solved problem.
Instead they came up with unpadded RSA, ECB-encrypted key blobs, a single shared key for all the blobs, a post-back proof that is just that broken RSA piped directly back to the server. I don't know, seems pretty bad?
Backup and sync-type software has the interesting engineering requirement that it is expected for the user's device to get completely lost/stolen/wiped, so any key material must be reproducible from the user's password.
Password -> KDF(1) gives you a password-alike: used for logins, server treats this kdf output as a password and stores a bcrypt/argon hash of it, as you would normally expect from a run-of-the-mill webapp.
The client generates a random data encryption key; seals it with the password; and then submits the sealed version to be stored in the user's profile on the web server.
The web server can't unseal the original data encryption key without the original password, and it never sees that, only the KDF(1) version of it.
That's all they've really done here. There is one more level of key indirection for the blobs themselves that i think is irrelevant but maybe useful for key rotation. Totally agree that unpadded RSA and ECB suck as primitives - they were bad choices then, they are bad choices now, and AEAD is a no-brainer upgrade (EDIT: and would close the post-back oracle) - but aside from picking better primitives the mechanism really does seem okay to me. I'd love to hear more from you though,
I think if you have a download link of the form https://foo.bar/#abcdef... you can simply put a large random value there (e.g. 128 bit), use HKDF to derive an ID and an encryption key, use the ID (shared with the server) to store/fetch encrypted data on/from the server and the key (not shared with the server) to encrypt/decrypt it on the client side. This would assume that the ID transmitted to the server over a secure channel and that brute-forcing of IDs to download encrypted data is not practical. Such a scheme would not be secure though if you derived the ID and key from a user-provided password, as the server could then brute-force the password from the ID the client provides.
You'd be surprised, but I've seen designers who managed to shoot themselves in the feet with SecretBox() calls alone. Anything more complex than using a library that does the crypto for you calls for an external/crypto team review.
Further, outside of Signal, whose authors won the RWC Levchin Prize for their design work, the other modern secure messengers essentially don't roll their own: they draft off the design work Signal did. Which is a good thing for their users. The alternative course, of coming up with your own special snowflake crypto, gets you papers like the one we're commenting on.
That doesn’t mean it was a great idea for them to pseudo-‘roll their own’, but it doesn’t deserve the vehement hatred that is constantly poured over it.
https://core.telegram.org/mtproto/description_v1
I honestly haven’t looked into anything newer from Telegram because it was pretty clearly a tire-fire and Signal was already a thing.
https://yro.slashdot.org/story/15/07/27/200204/interviews-ki...
>>The company has suffered from a hostile takeover by a Chinese investor who is wanted in China for fraud. He used a number of straw-men and businesses to accumulate more and more Mega shares. Recently his shares have been seized by the NZ government. Which means the NZ government is in control. In addition Hollywood has seized all the Megashares in the family trust that was setup for my children.
The filenames are stored as uuid in a local sqlite dB.
This runs on the mega.nz api
They are the cheapest storage service.
Who could have exploited the vulnerability?
Very few: An attacker would have had to first gain control over the
heart of MEGA’s server infrastructure or achieve a successful
man-in-the-middle attack on the user’s TLS connection to MEGA.
Who could have exploited the vulnerability?
We could have.You're the client, and you have a bucket of keys: keys for files, keys for chat, more keys for chat, &c. You encrypt them all with AES-ECB† under a "master key" which is in turn encrypted under a key derived from PBKDF2, so you can upload them to a server without revealing them to the server.
So the server has all these keys that you encrypted. You've got your password. Now you want to log in.
So what you do is you send an identifier (PKBDF2-derived from your password) to the server†. They look you up and they send you back one of those keys you uploaded before, the encrypted RSA key, along with a session ID encrypted under that RSA key. The idea is, you have the password and so you can decrypt the RSA key (by deriving the master key), and then decrypt the session ID and post it back to them so they know you're you.
The problem is these encrypted key blobs aren't authenticated; they're just the ECB ciphertext of the keys. And they do, like, no checking at all on them. So when they send you this RSA key blob (ostensibly the blob you sent them before, but of course, the server is malicious and so they tamper with it), they're just sending ECB(mk, [p, q, d, qInv, pad]) --- with that 4-tuple being length-delimited. The client just ECB-decrypts the blob and then makes sure it got 4 values.
So the first half of this paper is just 3 cryptographers doing stunt cryptography by randomizing qInv, the RSA CRT coefficient. The client obliviously uses whatever ECB decrypts here, and better yet, it uses it to perform an RSA operation on another ciphertext the server gets to choose, and better still, it then posts back the partial result of that encryption, so the server can see what happened and guess what to do next. And better yet, that RSA decryption is done with no meaningful padding: they just stick the session ID into a blob of zeroes; they don't even verify the padding, they just assume the session ID is the 43 bytes starting at offset 2 of the RSA plaintext, and ignore everything else.
They start by recovering the RSA key itself. They do this by recovering q, the first factor of the key. They can do this because by corrupting qInv and strategicially choosing RSA-encrypted session IDs, they can get back a session ID that is 0 if their current guess if below q, and nonzero if it's above q. A 1023-step binary search gets you q; you can get it down to 512 guesses using a lattice search that, as someone pointed out, is definitely going to be in a CTF level next year, now that scenarios like this can't be dunked on as entirely, ridiculously contrived. (From q you can quickly recover the rest of the key).
But this isn't even the craziest part. The craziest part is that all these other keys, a key per file or directory, are also encrypted under the same master key as that RSA key is. So when the server sends you the encrypted RSA key and blob encrypted under that RSA key, you can ECB-swap in blocks of other keys with carefully chosen session IDs to set up oracles to recover the other keys, based on how the client's RSA behaves with fucky qInv values. "We believe it to be an entirely novel kind of attack", they say. And to that I say, no shit it's novel, it's so novel Mega probably should have gotten an authorship credit on this paper: Backendal, Haller, Paterson, and Mega. They couldn't have done it --- or even thought of it --- without Mega.
Truly wonderful stuff.
† I know, I know, ECB, you can see penguins through it, but they're encrypting keys, which are fully random --- I mean, you assume they're fully random but just keep reading --- so it's not like completely unprecedented to see ECB here.
†† This is already terrible! All your security is that password, and they can attack it from this value!
They could also push an update which leaks the client-side keys directly?
Because each time I update a file the watchdog updates the cloud version, logging in then logging off after.
It's a service for pirates and other people who want to share content that would get pulled from services that can (trivially) view users' files
Their value proposition, is providing client-side encryption to their customers so they can protect their data in-transit and at rest. MEGA's job is to make it as unlikely as possible, and as expensive as possible for a threat actor to successfully thwart their value proposition. Vulnerabilities will always be discovered. Blessed practices will be superseded. This is normal.
In the consumer/end-user space, their storage to price ratio is great. Not counting plain mass storage filesystems for enterprise/development, I still hasn't found something better.
Still interesting research tho.
Just, I guess, take it under advisement for what designs don't work if you actually care about protecting user data.
The data of 0.25 billion users could quite easily be decrypted by whoever had access to MEGA’s systems (including governments and MEGA).
It also shows the importance of open source code. I suspect there are far more vulnerabilities and backdoors in closed source proprietary software.