Laboratory permeability data from the brine-filled Tubåen Formation in the Snøhvit field show an order of magnitude permeability variation for approximately the same porosity. This variation in permeability is explained by a modified Kozeny-Carman equation that exploits the relationships among permeability, porosity, cementation, and pore geometry. The expression correlates the slope in a logarithmic plot of porosity versus permeability with the amount of contact cement and sorting, and the intercept with the grain size. Additional information about sorting and/or cementation can be used to better constrain the slope of the plot. Based on this equation, we found that the grain size and the amount of contact cement increased with depth in the lowermost Tubåen 1–3 sandstone units, this led to an increasing permeability with depth, in the same porosity range. The permeability variation in the shallowest Tubåen 4 sandstone unit was affected by sorting to a larger degree than the remaining Tubåen intervals, which influenced the cementation factor, porosity, and permeability simultaneously. These findings were supported by the depositional environment of the formation, a petrology study of grain size and sorting and a rock-physics study. The rock-physics study indicated that the samples with higher permeability had higher elastic moduli compared with the samples with lower permeability. This correlation between permeability and elastic moduli can be explained by the increasing amount of contact cement for the stiffer, high-permeability samples.