Grupos que cambian: rotar la clave cuando alguien entra o sale

Un grupo estático es un problema resuelto: se genera una clave, se reparte y se acabó. Los grupos reales no son estáticos. Entra alguien nuevo el lunes, se va alguien el jueves, un dispositivo se pierde el viernes y hay que darlo de baja, y cada uno de esos sucesos exige que la clave con la que se cifra deje de ser la de antes. Hacerlo con dos personas es trivial; hacerlo con miles, de forma asíncrona, sin que nadie tenga que estar conectado, y garantizando que quien se fue no lea lo siguiente y que quien fue comprometido deje de serlo en la rotación siguiente, es un problema difícil que llevó años de trabajo académico y que hoy tiene un estándar del IETF. Esta lección explica qué resuelve ese estándar, sobre qué supuesto se apoya, por qué ese supuesto es exactamente el que un sistema local-first no puede pagar, y qué propiedad concreta hay que entregar a cambio de recuperarlo. La respuesta a esa última pregunta es lo más interesante del nivel entero.

Cada cambio de miembros es un cambio de clave

La ingenuidad inicial consiste en tener una clave por documento y recifrarlo entero cuando alguien sale. Falla por dos motivos distintos y ambos son definitivos. El primero es de coste: recifrar significa descargar, descifrar, volver a cifrar y volver a subir todo el corpus al que esa persona tenía acceso, en el dispositivo de quien ejecuta la baja, y con un corpus grande eso no termina nunca. El segundo es de eficacia: quien se va ya tenía el texto cifrado y ya tenía la clave antigua, de modo que recifrar no le quita nada que no tuviera. Se paga un coste enorme por una protección que no cubre lo que se creía cubrir.

El diseño correcto es el contrario y consiste en dejar de pensar en una clave y empezar a pensar en una sucesión de claves. El grupo atraviesa épocas; cada época tiene su propia clave; cada cambio de composición abre una época nueva; y lo que se cifró en una época queda cifrado bajo su clave para siempre. Quien se va conserva las claves de las épocas en las que estuvo, y eso es un hecho que hay que aceptar y comunicar. Lo que se consigue es acotar el daño: no lee lo que se escriba después, y quien haya visto comprometido un dispositivo deja de estar comprometido en cuanto se produzca una rotación con material fresco.

// Una epoca por cambio de composicion, con material fresco en cada salto
function aplicar(estado, propuesta) {
  const miembros = propuesta.tipo === 'quitar'
    ? estado.miembros.filter(m => m !== propuesta.quien)
    : [...estado.miembros, propuesta.quien];

  const claveNueva = derivar(estado.claveRaiz, aleatorioFresco());
  return { epoca: estado.epoca + 1, miembros, claveRaiz: claveNueva };
}

Esas dos protecciones tienen nombre propio en la literatura y conviene no confundirlas. El secreto hacia atrás dice que comprometer la clave de hoy no da acceso a los datos de ayer, y se consigue derivando cada clave de la anterior mediante una función irreversible. La seguridad tras compromiso dice que comprometer la clave de hoy deja de servir a partir de mañana, y se consigue mezclando aleatoriedad nueva que el atacante no vio en cada rotación. Una función irreversible sola da lo primero pero no lo segundo, porque el atacante puede seguir aplicándola hacia delante; hace falta inyectar material fresco para cortar esa continuidad.

Lo que resuelve el estándar y con qué supuestos

El protocolo de seguridad de capa de mensajería, publicado por el IETF como RFC 9420 en la vía de estándares, ataca exactamente este problema. Su resumen es preciso y merece citarse en lo esencial: establecimiento de clave de grupo asíncrono y eficiente, con secreto hacia atrás y seguridad tras compromiso, para grupos de tamaños que van de dos a miles. Existen implementaciones abiertas, entre ellas OpenMLS.

Su organización descansa en dos conceptos, grupos y épocas. La historia de un grupo se divide en una sucesión de épocas; en cada una, un conjunto de miembros autenticados acuerda un secreto de época conocido solo por quienes son miembros en esa época, y de ese secreto se derivan las demás claves. Cuatro objetos mueven el sistema: un paquete de claves que cada cliente publica para poder ser invitado, una propuesta que describe un cambio pendiente como añadir o quitar a alguien, una confirmación que abre efectivamente la época nueva, y un mensaje de bienvenida que da al recién llegado lo necesario para arrancar en la época en la que entra.

Debajo hay una estructura en árbol que es la que hace que el coste no crezca linealmente con el grupo. Los miembros ocupan las hojas de un árbol binario, cada nodo interno guarda material derivado de sus dos hijos y el secreto del grupo vive en la raíz. Renovar el material de un miembro consiste en recorrer el camino de su hoja hasta la raíz, actualizando los nodos de ese camino, que en un árbol equilibrado son del orden del logaritmo del número de miembros, con un caso peor lineal en ciertas condiciones.

flowchart TB
R[secreto de la epoca en la raiz] --> I1[nodo interno]
R --> I2[nodo interno]
I1 --> H1[hoja ana]
I1 --> H2[hoja bruno]
I2 --> H3[hoja carla]
I2 --> H4[hoja hueco tras una baja]
style R fill:#a6e3a1,color:#11111b
style H4 fill:#f38ba8,color:#11111b

El supuesto que un sistema sin servidor no puede pagar

Hay una palabra en la descripción anterior que decide todo lo que viene: la historia de un grupo es una sucesión lineal de épocas. Lineal significa que existe un orden total, y un orden total sobre operaciones concurrentes solo aparece si alguien lo impone. Ese alguien es el servicio de entrega: recibe las confirmaciones, las serializa, elige una cuando llegan dos a la vez y descarta o rechaza la perdedora. Es una función modesta que no requiere leer nada, y por eso convive sin problema con el cifrado, pero es una función que hay que tener.

El ejemplo canónico de por qué importa es corto. Ana añade a Carla al grupo mientras Bruno, a la vez, expulsa a Ana. Si la adición se procesa primero, Carla entra; si la expulsión se procesa primera, la adición de Ana queda anulada y Carla no entra. No hay ninguna verdad objetiva sobre cuál ocurrió antes: depende de la latencia de cada uno hasta el servidor y del orden en que el servidor los atienda. Lo que resuelve el caso no es la física sino la potestad del servidor para declarar un orden y comunicarlo.

Quitar el servidor quita esa potestad. Un sistema local-first admite por definición que alguien trabaje desconectado durante semanas y que sus operaciones se incorporen mucho después de haberse producido, de modo que las confirmaciones concurrentes no son una rareza sino el caso normal. Lo que queda entonces no es un orden total sino un orden causal: un orden parcial que dice que lo que alguien hizo después de ver algo depende de ese algo, y que deja sin ordenar lo que se hizo sin verse. Es exactamente la misma estructura de grafo dirigido acíclico que el recorrido lleva usando desde los niveles de convergencia, y se registra de forma local y eficiente con solo una función de resumen resistente a colisiones.

// Con orden causal no hay una epoca siguiente: hay varias, y todas son legitimas
const cabezas = [
  { epoca: 42, padre: 41, autor: 'ana',   op: 'anadir carla' },
  { epoca: 42, padre: 41, autor: 'bruno', op: 'quitar ana'   }
];
// Un servidor elegiria una. Sin servidor, el grupo se bifurca y hay que
// poder descifrar lo que se escribio en las dos ramas mientras duro la separacion.

El precio: tolerar concurrencia cuesta secreto hacia atrás

La comunidad ha explorado varias salidas y conviene conocerlas porque el espacio de diseño es pequeño y sus esquinas están bien delimitadas. Una línea es el acuerdo de clave de grupo continuo descentralizado propuesto por Weidner y Kleppmann, que no depende de servidor pero cuyo rendimiento es lineal en lugar de logarítmico, lo que lo sitúa en grupos del orden del centenar de miembros. Otra es una variante del árbol que solo exige orden causal en lugar de orden total, con rendimiento logarítmico, a cambio de necesitar una operación criptográfica asociativa y conmutativa para combinar actualizaciones concurrentes, y las opciones disponibles para eso son poco habituales y están mal servidas por las bibliotecas.

La tercera es la del proyecto Keyhive de Ink and Switch, cuyo planteamiento de partida es que en un contexto local-first no cabe dejar el control de acceso en manos de un proceso central y que la capa de autorización tiene que actuar como cimiento del resto. Su propuesta de acuerdo de claves se llama BeeKEM, está modelada sobre el árbol del estándar con ideas de la variante causal, no requiere servidor central, solo exige orden causal, mantiene el rendimiento logarítmico con caso peor lineal y se apoya únicamente en primitivas convencionales, intercambio de claves de Diffie Hellman y una función de resumen estándar.

La cuarta tarjeta nombra una clase de ataque que sencillamente no existe cuando hay un servidor que serializa, porque sin ramas no hay ataques entre ramas. Comprometer a un miembro en una bifurcación y aprovechar su estado para atacar secretos definidos en otra bifurcación concurrente es posible contra varios de los esquemas descentralizados propuestos, y por eso el trabajo de formalización de BeeKEM introduce una propiedad específica que lo cubre y que no tiene análogo en los modelos centralizados.

El compromiso de fondo se puede enunciar con precisión mediante un parámetro. Llámese al número de secretos individuales que cada miembro conserva en todo momento. Con uno solo, cada dispositivo guarda únicamente su material actual. Con más de uno, guarda también el anterior y el anterior a ese. Y aquí aparece la tensión: mantener más de uno elimina de hecho el secreto hacia atrás, porque quien se apodere del dispositivo obtiene material que abre secretos de grupo antiguos. Pero mantener más de uno es precisamente lo que hace falta para tolerar particiones, porque si Ana renueva su material mientras Bruno está desconectado y Bruno renueva el suyo a la vez, al reunirse ninguno podrá leer lo que el otro cifró salvo que haya conservado el material previo a la separación.