Introducing Passim: A Smarter Way to Check Password Similarity

Passwords are the gatekeepers of our digital lives, but let’s be real—they’re often a weak link. Users love to reuse passwords or make tiny tweaks like "Password123" to "Password124" when forced to reset. As developers, we want to enforce better habits without breaking security best practices. That’s where Passim comes in—a new open-source library I’ve been working on to tackle password similarity in a smart, secure way.

In this post, I’ll walk you through the problem Passim solves, how it works in its first version (v1) using n-grams, and where it’s headed with a cryptographic upgrade (v2) using homomorphic encryption. Whether you’re building a web app, a CLI tool, or a full-blown authentication system, Passim might just be the missing piece you didn’t know you needed.

The Problem: Passwords That Don’t Change Enough

Imagine you’re running a system where users reset their passwords. You’ve got a secure setup—passwords are hashed with bcrypt, salted for good measure, and stored safely. During a reset, a user changes "DogLover2023" to "DogLover2024". It’s technically a new password, but it’s so close to the old one that it barely improves security. How do you catch this without compromising your hash-only storage?

The catch is, hashes like bcrypt are one-way functions. You can’t peek at the original password to compare it—nor should you want to. Storing plaintext or reversible data is a security no-no. So, how do you check similarity when all you’ve got is a hash? That’s the puzzle Passim solves.

Passim v1: The N-Gram Approach

For the first version of Passim, I went with a practical, lightweight solution: n-grams. Here’s how it works:

How It Works

1. Hash the Password: When a user sets a password (say, "Password123"), Passim hashes it with bcrypt. This is your standard, secure storage step.

2. Create a Similarity Sketch: Alongside the hash, Passim breaks the password into n-grams—small, overlapping chunks (e.g., trigrams: "Pas", "ass", "ssw", etc.). Each n-gram gets hashed with a fast algorithm (SHA-256, truncated for efficiency), and we store a fixed-size set of these hashed n-grams (say, 5 of them).

3. Check Similarity: During a reset, the user submits a new password ("Password124"). Passim generates its n-gram sketch and compares it to the old sketch. If too many hashed n-grams match (e.g., 50% overlap), it flags the new password as "too similar" and rejects it.

4. Update if Good: If the new password passes (like "TotallyNew"), it gets hashed and stored with a fresh sketch, replacing the old data.

Why N-Grams?

N-grams are great because they capture the structure of a password without revealing the whole thing. "Password123" and "Password124" share a lot of trigrams ("Pas", "ass", "wor", etc.), while "TotallyNew" doesn’t. It’s a simple way to measure similarity without needing the plaintext.

Code Sneak Peek

Here’s how you’d use Passim in Python:

from passim import Passim

p = Passim()
hash_, sketch = p.store_password("Password123")
is_similar = p.check_similarity(sketch, "Password124")  # True
success, (new_hash, new_sketch) = p.change_password(hash_, sketch, "TotallyNew")  # Accepted

And in TypeScript:

import { Passim } from 'passim';

const p = new Passim();
(async () => {
    const [hash, sketch] = await p.storePassword("Password123");
    const isSimilar = p.checkSimilarity(sketch, "Password124");  // true
    const [success] = await p.changePassword(hash, sketch, "TotallyNew");  // true
})();

The Catch

N-grams work well, but they’re not perfect. Those hashed n-grams could leak structural hints—like common chunks ("123" or "abc")—if an attacker gets hold of them. It’s not a dealbreaker for most systems (especially with proper storage security), but it’s a risk I wanted to address.

Passim v2: Going Cryptographic with Homomorphic Encryption

That’s where the next version comes in. For v2, I’m planning to ditch n-grams and use homomorphic encryption (HE)—a mind-bending crypto technique that lets you compute on encrypted data without decrypting it. Here’s the vision:

The Upgrade Plan

• Encrypt Features: Instead of n-grams, extract features like character frequencies ("P:1, a:2, s:2...") from the password, encrypt them with something like Paillier HE, and store them alongside the bcrypt hash.

• Compare Encrypted: When a new password comes in, encrypt its features and run a similarity check (e.g., cosine similarity) directly on the encrypted data. Decrypt only the final similarity score to decide if it’s too close.

• Zero Leakage: Unlike n-grams, this leaks nothing about the password’s structure—everything stays encrypted until the last step.

It’s heavier computation-wise, but the security boost is worth it for high-stakes systems. Think of v1 as the fast, practical baseline and v2 as the Fort Knox edition

Why Passim?

here are tons of password libraries out there, so why build Passim? Most focus on hashing or strength validation (e.g., "add a special character!"), but few tackle similarity across resets. Passim fills that gap with:

• Flexibility: Works in Python and TypeScript, server or client-side.

• Configurability: Tweak n-gram size, similarity thresholds, etc., to fit your needs.

• Security-First: Balances usability with best practices, evolving toward cutting-edge crypto.

Get Involved

Passim v1 is live now—grab it on PyPI (pip install passim) or npm (npm install passim). It’s MIT-licensed, so fork it, tweak it, or just play around. Check the repos for Python (github.com/nasredeenabdulhaleem/passim) and TypeScript (github.com/nasredeenabdulhaleem/passim-ts).

Got ideas? Found a bug? Open an issue or PR—I’d love to hear from you. And stay tuned for v2, where we’ll take password security to a whole new level with homomorphic magic.

Happy coding, and here’s to stronger passwords!

Abdulhaleem Nasredeen