Formal Verification of the Signal Protocol Using AI

This seems like a good thing:

Google Deepmind researchers used agentic AI to mathematically prove, or “formally verify,” a number of the Signal protocol’s key cryptographic guarantees­a landmark development for the widely used cryptography and AI itself.

Conducted as a sort of proof-of-concept project in just four weeks, the work is significant in two ways. It serves as further independent validation of the cryptography that protects massive quantities of the world’s communications on platforms like the Signal app, Google Messages, and WhatsApp. And it demonstrates Google DeepMind’s formal verification capabilities using a new AI framework called AlphaProof Code.

[…]

The DeepMind analysis did not find any new vulnerabilities in the portions of the Signal protocol it looked at, but when the researchers used AlphaProof Code on older versions of Signal that contain known and long-fixed vulnerabilities, it correctly identified them and showed that the protocol could not be formally verified. The researchers are releasing the specification and proof they developed for the Signal protocol analysis to aid other formal verification work.

Alternate link.

Details:

First, our researchers collaborated with a mix of models to translate Signal’s security goals into formal mathematical specifications, with human experts reviewing every one. From there, agents powered by Gemini Carbon did the proofs, generating over six million lines of Lean, a computer language that mathematically proves the accuracy of code.

Next, the agents audited the proof and highlighted areas that needed a second look by a human ­ just one percent of the codebase, a massive time savings. Because Lean automatically checks the rest, our experts could focus their review where human judgment matters most.

Technical paper.

Posted on November 17, 2026 at 7:05 AM • 15 Comments

Comments

dsanford0 • November 17, 2026 7:53 AM

In the age of AI coding, where prompts and other obfuscated information may be embedded in code, I favor much more formal verification. Many programs are fairly simple finite-state machines, which should be easy to verify.

Clive Robinson • November 17, 2026 8:51 AM

Hmm,

Any one up for a long read,

“generating over six million lines of Lean, a computer language that mathematically proves the accuracy of code.
“

How long does it take you to read a “leisure read paperback” that is approximately 10,000 lines over 350 pages?

How about a basic undergrad type text book of similar size?

Who is going to read it all?

But then who is going to be able to take it all in?

And that is all before the $64,000 question about LLMs and the issues they have with things that were not in their training data…

Rontea • November 17, 2026 9:43 AM

Validating the cryptographic guarantees behind tools like Signal, WhatsApp, and Google Messages is no small feat, and doing it in just four weeks demonstrates the potential impact on software assurance. That said, scaling this approach to full applications and large codebases will be the real challenge. High-assurance sectors—finance, government, defense—will watch closely to see if such AI-driven verification can become practical at scale without prohibitive cost or effort.

Clive Robinson • November 17, 2026 9:49 AM

@ JG6,

With regards,

“If you don’t have end-point security, you’ve got worse than nothing.”

Yup…

“It’s easy to have a a strong link in an otherwise weak chain, do more harm than all the weak links combined.”

I’ve always wondered why people only talk about the “strong links” but not the overall system.

Back when Signal and other supposedly “secure apps” came out I pointed out the problems with the “security end point” and the “communications end point” and how the OS allowed “end run attacks”, and effectively painted a target on your back…

It took a while for this to sink in with those who could think about it rationally, but many others either can not or chose not to think about it rationally.

The reasons are sadly,

1, Convenience of use.
2, Because others in their group use it.

And it goes wrong in many ways including some that became seriously embarrassing for those in Politics.

Now of course using “Signal” or other “supposedly secure messaging apps” is not really going to be secure any longer…

Because, Apple, Google and now Microsoft have built in “Client Side Scanning” into their OS’s in ways you can not avoid/prevent the “ET phone home to the mothership”.

All as part of the “Think of the Children” nonsense supposedly to catch CSAM. But now the CSS mechanism is in the OS expanding it to other things is in effect trivial…

People need to wake up to the fact that the “Anti-E2EE” game is over as long as the “they” can get at the “User Interface” that is “human usable” plaintext and send it back to the “they” over the “communications interface” that the OS suppliers do their best to stop you securing”.

It’s why I’ve said for quite some time that the “security end point” should be on a separate device beyond the device that has the “communications end point”.

I’ve described a way to have a secure endpoint by use of a hand cipher using just paper and pencil a couple of times on this blog…

Yet it won’t be used by people because,

“It lacks ‘all in one, thought free’ convenience…”

Which is why it is also “oh so easy” for the “they” of even “Level 1 Attackers” to abuse thus use against you.

Weather • November 17, 2026 5:18 PM

@Bruce

Hacker mind set, not many people in the position have that, its type of some one told me, so must be accurate.

Its the training data, for Google search instead of going to ipv6.

Sure it finds some random unknown auther and copies it, and all of a sudden Ai can do incredible things.

Esa is missing the Msb being low values, you can cut the space in half.

Why are we working with bytes instead of dwords.

Magnus • November 17, 2026 7:28 PM

“six million lines of Lean”

One of the problems that mathematicians (real mathematicians) brought up about AI slop-proofs, while everyone else was saying AI has or will soon “solve maths”, is that the proofs are impenetrable, convoluted, long, and don’t contribute any useful techniques or insights.

How is anyone supposed to go through 6 millions lines of slop? Well the whole point is it’s automatically verifiable. We’re told. The bots even found bugs, and fixed them, in Lean itself! So it’s bulletproof! Which is supposed to be reassuring.

I’ve still got a copy of that old Reflectctions on Trusting Trust paper lying around somewhere…

cybershow • November 18, 2026 3:09 AM

Got as far as the word Google and turned away. I am in no position to read
six million lines, nor a smart and patient enough mathematician to satisfy
myself even if could. Trust, which lies at the root of all important affairs,
cannot possibly come from an organisation like Alphabet. Why would anyone
believe a for-profit whose business model is surveillance and which cannot
keep a chief ethicist in post for more than a few months? Formal proofs are
very important. But they must come from free and independent sources and be
peer reviewed by an international community of recognised experts – not from
a thinly veiled arm of US government with big and expensive machines.
Otherwise we’re just back to trusting the NSA to tell NIST what encryption
algorithms are best.

Hacketry • November 18, 2026 8:04 AM

Hopefully Linux and the Linux kernel can be vetted for vulns, since many embedded systems and routers use Linux.

Clive Robinson • November 18, 2026 9:20 AM

@ Hacketry, ALL,

With regards,

“… can be vetted for vulns, since many embedded systems and routers use Linux.”

Whilst it might be fun to find vulnerabilities in “embedded systems and routers” mostly there is little that can be done with such systems.

Many “embedded systems and routers” can not be updated or patched for various reasons. Which means that the only two routes open to an owner are,

1, Rip out and replace.
2, Mitigate the device.

Either way it is likely to require “hands on physical” intervention with replacement parts.

freedom • November 18, 2026 9:37 AM

Magnus, Clive

Any one up for a long read,
How is anyone supposed to go through 6 millions lines of slop?

It’s pretty easy! You feed the 6 million lines “proof” to another chatbot, and the chartbot will :
1) tell you everything is fine
2) it will give you a 60 million lines “proof’ of the previos “proof”. You can check this new “proof” yourself

Isn’t “AI” amazing?

freedom • November 18, 2026 9:49 AM

Cybershow,

Why would anyone believe a for-profit whose business model is surveillance

Well here’s some great news! You can “verify” this “AI” thing using…”AI”!!

It’s like the bible. The bible is true because god wrote it. And we know that god wrote it because the bible says so.

Wannabe Techguy • November 18, 2026 11:26 AM

@Cybershow

“Otherwise we’re just back to trusting the NSA to tell NIST what encryption
algorithms are best.”
Are you implying NSA can’t be trusted?

Clive Robinson • November 18, 2026 4:20 PM

@ Wannabe Techguy, Cybershow, ALL,

With regards,

“Are you implying NSA can’t be trusted?”

Not sure if you are being sarcastic or not… But on the assumption you are not,

I’ve said it before quite a few times going back over the years.

Look up the term “finessing” it is a term that originated with the “card game” called Bridge. It was quite popular at Bletchley Park, and there it got used as kind of code word for certain activities.

Due to the BRUSA agreement what became GCHQ and the NSA had very tight relations over and above anything the respective countries politicians and more general Civil Servants had knowledge of (it’s also why so many UK RAF Bases are in reality little pieces of the US).

Then look up the relationship with William Friedman of the NSA and Boris Hagelin the founder of Crypto AG zug Switzerland. And that the company was later acquired by German and US intelligence in the 1970’s with Swiss Intelligence in the game as well. And how the death of Boris Hagelin’s son brought up questions that revealed the “finessing” that was “Operation Rubicon”,

https://inteltoday.org/2026/09/09/five-years-ago-crypto-ag-was-boris-hagelin-jr-murdered-by-the-cia-update-the-scandalous-history-of-the-last-rotor-cipher-machine/

Then more recently was the AES competition where the NSA were Advising NIST. It appears the competition rules were “fixed” such that a version of the cipher that had very bad side channel issues due to “loop unrolling” was released to the public and ended up in many software libraries (with quite a few still in use).

Fun thing whilst the NSA approved AES it was only for “data at rest” not whilst encrypting or decrypting data.

There were better crypto candidates in the AES competition but… The rules in effect pushed what became the finalist that had potentially the worst side channel issues.

Then there was the embarrassment of the Dual Elliptic Curve Digital Random Bit Generator and RSA and Juniper Networks making it “the default”.

And a whole load of other poorly done finesses over the years that have come to light over the years.

Hacketry • November 18, 2026 8:26 PM

@ Clive, ALL,

You’re probably correct about most routers and especially about embedded systems.
About routers, the most people can do is buy routers that can have firmware updates, such as routers running OpenWrt (and of course install the updates).

Leave a comment

Blog moderation policy

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.