Potential collision in `hash`

[SukkaW]

cc @thysultan

stylis contains a dead simple hash function used for matching CSS properties, and I am wondering how safe it is. So I write a small PoC:

const { hash, charat } = require('stylis');
const { all } = require('known-css-properties');

function djb2a (value, length) {
    let h = 5381;
    for (let i = 0; i < length; i++) {
        h = ((h << 5) + h) ^ charat(value, i)
    }
    return h >>> 0
}

function getCollidedFromHashMap (obj) {
  return Object.fromEntries(Object.entries(obj).filter(([key, value]) => value.length > 1));
};

const stylisHashMap1 = {};

all.forEach(property => {
  if (property.startsWith('-')) {
    const key = hash(property, property.length);
    stylisHashMap1[key] = stylisHashMap1[key] || [];
    stylisHashMap1[key].push(property);
  }
});

const stylisHashMap2 = {};

all.forEach(property => {
  if (!property.startsWith('-')) {
    const key = hash(property, property.length);
    stylisHashMap2[key] = stylisHashMap2[key] || [];
    stylisHashMap2[key].push(property);
  }
});

const djb2aHashMap = {};

all.forEach(property => {
  if (!property.startsWith('-')) {
    const key = djb2a(property, property.length);
    djb2aHashMap[key] = djb2aHashMap[key] || [];
    djb2aHashMap[key].push(property);
  }
});

console.log('(stylis) Collided all known css properties with vendor prefixed only:');
console.log(getCollidedFromHashMap(stylisHashMap1));
console.log('(stylis) Collided all known css properties without vendor prefixed:');
console.log(getCollidedFromHashMap(stylisHashMap2));
console.log('(djb2a) Collided all known css properties:');
console.log(getCollidedFromHashMap(djb2aHashMap));

You can test the PoC out at ReplIt: https://replit.com/@SukkaW/QuarterlyMotherlyCollaborativesoftware

The result is that the stylis' built-in hash is not safe at all. And honestly, that is not a surprising result. The current hash function only takes in the first, the second, and the third characters and the length into the account. So any CSS properties that have the same length and the first three characters are the same will collided.

E.g. flex-flow, flex-grow, and flex-wrap all have the same hash 6060, while the stylis is matching 6060 for flex-grow:

https://github.com/thysultan/stylis/blob/55c363f844a20b983d1dcee68be35716b393ee5d/src/Prefixer.js#L65-L67

And mask-(border|origin|repeat) all have the same hash 6135, but the stylis only need to prefix mask-(repeat|origin):

https://github.com/thysultan/stylis/blob/55c363f844a20b983d1dcee68be35716b393ee5d/src/Prefixer.js#L19-L20

And transform and translate all have the same hash 4810, but the stylis only need to prefix transform:

https://github.com/thysultan/stylis/blob/55c363f844a20b983d1dcee68be35716b393ee5d/src/Prefixer.js#L27-L29

And many other collisions, like:

• scroll-margin-top and scroll-snap-align all have the same hash 2647 but the stylis only needs to prefix the scroll-margin-top.
• scroll-margin-left, scroll-padding-top and scroll-snap-margin all have the same hash 2391 but the stylis only needs to prefix the scroll-margin-left.

[thysultan]

Is it only mask-border, scroll-snap-align, scroll-padding-top, scroll-snap-margin that are getting extra prefixes?

[SukkaW]

Is it only mask-border, scroll-snap-align, scroll-padding-top, scroll-snap-margin that are getting extra prefixes?

I only select a few from those collided. There are probably more since my PoC doesn't filter them out.

[thysultan]

Hashing collisions are expected in this case. We should narrow it down to only the ones that are prefixed in the switch block and that shouldn't, and then evaluate if it is within acceptable tolerance.

[layershifter]

I am doing a custom prefixer and re-use hash() function, the collision happened there:

console.log('hash:background-clip', hash('background-clip', 'background-clip'.length)); // 4215
console.log('hash:backdrop-filter', hash('backdrop-filter', 'backdrop-filter'.length)); // 4215

I would like to prefix only backdrop-filter, but due hash collision both will be prefixed without additional checks.

[Andarist]

once u know about the collision you could always discriminate inputs based on a unique character in all candidates

[SukkaW]

Hi, it is 2024 and I am back to the issue here.

once u know about the collision you could always discriminate inputs based on a unique character in all candidates

@Andarist I am afraid this is a huge task.

Here I use a simple script to collect all known CSS properties collision:

const { hash, charat } = require("stylis");
const { all } = require("known-css-properties");

function djb2a(value, length) {
  let h = 5381;
  for (let i = 0; i < length; i++) {
    h = ((h << 5) + h) ^ charat(value, i);
  }
  return h >>> 0;
}

function getCollidedFromHashMap(obj) {
  return Object.fromEntries(
    Object.entries(obj).filter(([key, value]) => value.length > 1),
  );
}

const stylisHashMap1 = {};

const nonPrefixedProperties = all.filter((i) => !i.startsWith("-"));

nonPrefixedProperties.forEach((property) => {
  const key = hash(property, property.length);
  stylisHashMap1[key] ||= [];
  stylisHashMap1[key].push(property);
});

const stylisHashMap2 = {};

nonPrefixedProperties.forEach((property) => {
  const key = hash(property, property.length);
  stylisHashMap2[key] ||= [];
  stylisHashMap2[key].push(property);
});

const djb2aHashMap = {};

all.forEach((property) => {
  if (!property.startsWith("-")) {
    const key = djb2a(property, property.length);
    djb2aHashMap[key] = djb2aHashMap[key] || [];
    djb2aHashMap[key].push(property);
  }
});

console.log("(stylis) Collided all known css properties:");
console.log(getCollidedFromHashMap(stylisHashMap1));
// console.log('(stylis) Collided all known css properties without vendor prefixed:');
// console.log(getCollidedFromHashMap(stylisHashMap2));
console.log("(djb2a) Collided all known css properties:");
console.log(getCollidedFromHashMap(djb2aHashMap));

https://replit.com/@isukkaw/DarkkhakiRealisticCharmap#index.js

And here is the collision result:

{
  '87': [ 'scroll-padding-inline-start', 'scrollbar-dark-shadow-color' ],
  '343': [
    'scroll-margin-inline-start',
    'scroll-padding-block-start',
    'scrollbar-darkshadow-color'
  ],
  '599': [
    'scroll-margin-block-start',
    'scroll-padding-inline-end',
    'scroll-snap-margin-bottom',
    'scrollbar-highlight-color'
  ],
  '708': [
    'text-decoration-overline',
    'text-decoration-skip-box',
    'text-decoration-skip-ink'
  ],
  '855': [
    'scroll-margin-inline-end',
    'scroll-padding-block-end',
    'scroll-snap-margin-right'
  ],
  '964': [
    'text-decoration-skip-self',
    'text-decoration-thickness',
    'text-decoration-underline'
  ],
  '1094': [ 'overflow-clip-margin-left', 'overscroll-behavior-block' ],
  '1606': [ 'overflow-clip-margin-bottom', 'overflow-clip-margin-inline' ],
  '1641': [ 'animation-iteration-count', 'animation-timing-function' ],
  '1756': [
    'border-bottom-left-radius',
    'border-inline-start-color',
    'border-inline-start-style',
    'border-inline-start-width',
    'border-start-start-radius'
  ],
  '1862': [
    'overflow-clip-margin-block',
    'overflow-clip-margin-right',
    'overscroll-behavior-inline'
  ],
  '2012': [
    'border-block-start-color',
    'border-block-start-style',
    'border-block-start-width'
  ],
  '2038': [ 'epub-text-emphasis-color', 'epub-text-emphasis-style' ],
  '2104': [ 'hyphenate-limit-last', 'hyphenate-limit-zone' ],
  '2118': [ 'overscroll-behavior-x', 'overscroll-behavior-y' ],
  '2135': [
    'scroll-margin-block',
    'scroll-margin-right',
    'scroll-padding-left'
  ],
  '2236': [ 'font-language-override', 'font-variant-ligatures' ],
  '2244': [ 'text-emphasis-skip', 'text-kashida-space', 'text-overline-mode' ],
  '2250': [
    'transition-behavior',
    'transition-duration',
    'transition-property'
  ],
  '2268': [
    'border-end-start-radius',
    'border-inline-end-color',
    'border-inline-end-style',
    'border-inline-end-width',
    'border-start-end-radius',
    'border-top-right-radius'
  ],
  '2291': [
    'marker-knockout-left',
    'view-timeline-axis',
    'view-timeline-name'
  ],
  '2360': [ 'hyphenate-limit-chars', 'hyphenate-limit-lines' ],
  '2389': [ 'position-animation', 'position-try-order' ],
  '2391': [
    'scroll-margin-left',
    'scroll-padding-top',
    'scroll-snap-margin',
    'scroll-snap-type-x',
    'scroll-snap-type-y'
  ],
  '2492': [
    'font-synthesis-position',
    'font-variant-alternates',
    'font-variant-east-asian',
    'font-variation-settings'
  ],
  '2500': [
    'text-emphasis-color',
    'text-emphasis-style',
    'text-overline-color',
    'text-overline-style',
    'text-overline-width',
    'text-underline-mode'
  ],
  '2506': [ 'transform-origin-x', 'transform-origin-y', 'transform-origin-z' ],
  '2524': [
    'border-block-end-color',
    'border-block-end-style',
    'border-block-end-width',
    'border-top-left-radius'
  ],
  '2547': [ 'marker-knockout-right', 'view-timeline-inset' ],
  '2599': [ 'stroke-alignment', 'stroke-dasharray' ],
  '2647': [ 'scroll-margin-top', 'scroll-snap-align' ],
  '2665': [ 'animation-composition', 'animation-range-start' ],
  '2679': [
    'background-attachment',
    'background-blend-mode',
    'background-position-x',
    'background-position-y'
  ],
  '2748': [ 'font-synthesis-style', 'font-variant-numeric' ],
  '2756': [ 'text-group-align', 'text-orientation', 'text-size-adjust' ],
  '2793': [ 'page-break-before', 'page-break-inside' ],
  '2855': [
    'stroke-dashadjust',
    'stroke-dashcorner',
    'stroke-dashoffset',
    'stroke-miterlimit'
  ],
  '2903': [ 'scroll-snap-stop', 'scroll-snap-type', 'scrollbar-gutter' ],
  '3004': [
    'font-feature-settings',
    'font-synthesis-weight',
    'font-variant-position'
  ],
  '3012': [ 'text-justify-trim', 'text-line-through', 'text-spacing-trim' ],
  '3018': [ 'transform-origin', 'transition-delay' ],
  '3049': [ 'page-break-after', 'page-orientation' ],
  '3159': [
    'scroll-margin-block-end',
    'scroll-snap-destination',
    'scroll-snap-margin-left',
    'scrollbar3d-light-color'
  ],
  '3177': [
    'animation-direction',
    'animation-fill-mode',
    'animation-range-end'
  ],
  '3191': [
    'backface-visibility',
    'background-position',
    'background-repeat-x',
    'background-repeat-y'
  ],
  '3227': [
    'layout-grid-char',
    'layout-grid-line',
    'layout-grid-mode',
    'layout-grid-type'
  ],
  '3268': [ 'text-emphasis-position', 'text-line-through-mode' ],
  '3292': [
    'border-bottom-color',
    'border-bottom-style',
    'border-bottom-width',
    'border-image-outset',
    'border-image-repeat',
    'border-image-source',
    'border-inline-color',
    'border-inline-start',
    'border-inline-style',
    'border-inline-width'
  ],
  '3319': [ 'mask-border-mode', 'mask-source-type' ],
  '3360': [ 'grid-template-rows', 'supported-color-schemes' ],
  '3415': [
    'scroll-snap-coordinate',
    'scroll-snap-margin-top',
    'scrollbar-shadow-color',
    'scrollbar3dlight-color'
  ],
  '3433': [ 'animation-duration', 'animation-timeline' ],
  '3524': [
    'text-line-through-color',
    'text-line-through-style',
    'text-line-through-width',
    'text-underline-position'
  ],
  '3548': [
    'border-block-color',
    'border-block-start',
    'border-block-style',
    'border-block-width',
    'border-image-slice',
    'border-image-width',
    'border-right-color',
    'border-right-style',
    'border-right-width'
  ],
  '3575': [ 'mask-border-slice', 'mask-border-width' ],
  '3616': [ 'grid-auto-columns', 'grid-column-start' ],
  '3671': [
    'scroll-padding-bottom',
    'scroll-padding-inline',
    'scrollbar-arrow-color',
    'scrollbar-track-color'
  ],
  '3703': [ 'background-origin', 'background-repeat' ],
  '3780': [
    'text-combine-upright',
    'text-decoration-line',
    'text-decoration-none',
    'text-decoration-skip',
    'text-decoration-trim',
    'text-underline-color',
    'text-underline-style',
    'text-underline-width'
  ],
  '3804': [
    'border-inline-end',
    'border-left-color',
    'border-left-style',
    'border-left-width'
  ],
  '3829': [ 'column-rule-color', 'column-rule-style', 'column-rule-width' ],
  '3830': [ 'epub-caption-side', 'epub-text-combine', 'epub-writing-mode' ],
  '3831': [ 'mask-border-outset', 'mask-border-repeat', 'mask-border-source' ],
  '3839': [ 'descent-override', 'margin-block-start' ],
  '3927': [
    'scroll-margin-bottom',
    'scroll-margin-inline',
    'scroll-padding-block',
    'scroll-padding-right',
    'scroll-snap-points-x',
    'scroll-snap-points-y',
    'scroll-timeline-axis',
    'scroll-timeline-name',
    'scrollbar-base-color',
    'scrollbar-face-color'
  ],
  '3959': [ 'background-color', 'background-image' ],
  '3999': [ 'block-step-align', 'block-step-round' ],
  '4036': [
    'text-decoration-blink',
    'text-decoration-color',
    'text-decoration-style',
    'text-underline-offset'
  ],
  '4060': [
    'border-block-end',
    'border-top-color',
    'border-top-style',
    'border-top-width'
  ],
  '4075': [ 'perspective-origin-x', 'perspective-origin-y' ],
  '4116': [ 'wrap-before', 'wrap-inside' ],
  '4128': [ 'grid-column-end', 'grid-column-gap' ],
  '4129': [ 'ruby-align', 'ruby-merge', 'string-set' ],
  '4140': [ 'outline-color', 'outline-style', 'outline-width' ],
  '4200': [ 'justify-self', 'rest-before' ],
  '4201': [ 'animation-delay', 'animation-range' ],
  '4215': [ 'backdrop-filter', 'background-clip', 'background-size' ],
  '4279': [ 'pause-after', 'voice-rate' ],
  '4316': [ 'border-boundary', 'border-collapse' ],
  '4351': [ 'margin-block', 'margin-break', 'margin-right' ],
  '4361': [ 'inset-inline', 'motion-offset' ],
  '4384': [ 'grid-auto-flow', 'grid-auto-rows', 'grid-row-start' ],
  '4391': [ 'place-self', 'stroke-size' ],
  '4427': [ 'offset-anchor', 'offset-rotate' ],
  '4456': [ 'justify-items', 'rest-after' ],
  '4519': [ 'bookmark-label', 'bookmark-level', 'bookmark-state' ],
  '4535': [ 'voice-pitch', 'voice-range' ],
  '4548': [ 'text-anchor', 'text-indent', 'text-shadow' ],
  '4604': [ 'container-name', 'container-type' ],
  '4607': [ 'margin-bottom', 'margin-inline' ],
  '4678': [ 'overflow-anchor', 'overflow-inline', 'override-colors' ],
  '4693': [ 'break-before', 'break-inside' ],
  '4765': [ 'float-offset', 'max-block-size' ],
  '4796': [
    'font-display',
    'font-kerning',
    'font-palette',
    'font-stretch',
    'font-variant'
  ],
  '4810': [ 'transform', 'translate' ],
  '4828': [ 'border-bottom', 'border-inline', 'border-radius' ],
  '4851': [ 'marker-pattern', 'marker-segment' ],
  '4896': [ 'grid-row-end', 'grid-row-gap' ],
  '4908': [ 'display-align', 'outline-offset' ],
  '4909': [ 'object-position', 'object-view-box' ],
  '4939': [ 'offset-distance', 'offset-position', 'offset-rotation' ],
  '5084': [
    'border-block',
    'border-color',
    'border-image',
    'border-right',
    'border-style',
    'border-width'
  ],
  '5103': [ 'color-adjust', 'color-scheme' ],
  '5109': [ 'column-count', 'column-width' ],
  '5111': [ 'mask-position-x', 'mask-position-y' ],
  '5159': [ 'stroke-linecap', 'stroke-opacity' ],
  '5207': [
    'scroll-behavior',
    'scroll-timeline',
    'scrollbar-color',
    'scrollbar-width'
  ],
  '5221': [ 'nav-down', 'nav-left' ],
  '5245': [ 'caret-color', 'caret-shape' ],
  '5308': [ 'font-style', 'font-width' ],
  '5316': [
    'text-align-all',
    'text-autospace',
    'text-rendering',
    'text-transform',
    'text-underline',
    'text-wrap-mode'
  ],
  '5324': [ 'fill-break', 'fill-color', 'fill-image' ],
  '5365': [ 'column-fill', 'column-rule', 'column-span' ],
  '5415': [ 'stroke-linejoin', 'stroke-position' ],
  '5453': [ 'line-grid', 'line-snap' ],
  '5477': [ 'inherits', 'nav-index', 'nav-right' ],
  '5533': [ 'float-defer', 'max-lines', 'max-width' ],
  '5535': [ 'block-size', 'block-step' ],
  '5564': [ 'font-family', 'font-weight' ],
  '5565': [ 'box-shadow', 'box-sizing' ],
  '5572': [ 'text-align-last', 'text-decoration', 'text-wrap-style' ],
  '5580': [ 'fill-origin', 'fill-repeat' ],
  '5604': [ 'padding-bottom', 'padding-inline' ],
  '5623': [ 'mask-clip', 'mask-mode', 'mask-size', 'mask-type' ],
  '5671': [
    'place-content',
    'stroke-align',
    'stroke-break',
    'stroke-color',
    'stroke-image',
    'stroke-width'
  ],
  '5708': [ 'fallback', 'stop-opacity' ],
  '5709': [ 'line-break', 'line-clamp' ],
  '5815': [ 'voice-family', 'voice-stress', 'voice-volume' ],
  '5828': [ 'text-justify', 'text-kashida', 'text-spacing' ],
  '5844': [ 'clip-path', 'clip-rule' ],
  '5860': [ 'padding-block', 'padding-right' ],
  '5864': [ 'math-depth', 'math-shift', 'math-style' ],
  '5875': [ 'marker-end', 'marker-mid', 'viewport-fit' ],
  '5897': [ 'inset-area', 'motion-path' ],
  '5920': [ 'grid-gap', 'grid-row' ],
  '5921': [ 'ruby-overhang', 'ruby-position' ],
  '5927': [ 'stroke-origin', 'stroke-repeat' ],
  '5958': [ 'overflow-x', 'overflow-y' ],
  '6027': [ 'flow-from', 'flow-into' ],
  '6043': [ 'layout-flow', 'layout-grid' ],
  '6060': [ 'flex-flow', 'flex-grow', 'flex-wrap' ],
  '6068': [ 'shape-inside', 'shape-margin' ],
  '6071': [ 'pause-before', 'voice-balance' ],
  '6084': [
    'text-box-edge',
    'text-box-trim',
    'text-emphasis',
    'text-overflow',
    'text-overline'
  ],
  '6092': [ 'fill-rule', 'fill-size' ],
  '6131': [ 'marker-side', 'view-timeline', 'viewport-fill' ],
  '6135': [ 'mask-border', 'mask-origin', 'mask-repeat' ],
  '6143': [ 'margin-left', 'margin-trim' ],
  '6396': [ 'contain', 'content' ]
}

[Andarist]

Honestly, I don't quite have the bandwidth and mental space to handle this right now. Note that usually some extra prefixes shouldn't introduce actual errors to your applications. A big problem would be if some of the generated ones are plain incorrect and that they could be fine-tuned to make them work.

[thysultan]

@SukkaW Collisions are expected, A better test for this would be to run it against the prefix function in src/Prefixer.js instead of the hash function as we only really care about the properties we actually prefix, and looking at the collision list it looks like there's non that we don't already handle for.